字符串循环移位包含

s1 = AABCD, s2 = CDAA
Return : true

给定两个字符串 s1 和 s2，要求判定 s2 是否能够被 s1 做循环移位得到的字符串包含。

s1 进行循环移位的结果是 s1s1 的子字符串，因此只要判断 s2 是否是 s1s1 的子字符串即可。

字符串循环移位

s = "abcd123" k = 3
Return "123abcd"

将字符串向右循环移动 k 位。

将 abcd123 中的 abcd 和 123 单独翻转，得到 dcba321，然后对整个字符串进行翻转，得到 123abcd。

字符串中单词的翻转

s = "I am a student"
Return "student a am I"

将每个单词翻转，然后将整个字符串翻转。

151. 翻转字符串里的单词

难度：中等

给定一个字符串，逐个翻转字符串中的每个单词。

示例 1：

输入: "the sky is blue"
输出: "blue is sky the"

示例 2：

输入: "  hello world!  "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

示例 3：

输入: "a good   example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

说明：

• 无空格字符构成一个单词。
• 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
• 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

进阶：

请选用 C 语言的用户尝试使用 O(1) 额外空间复杂度的原地解法。

先将字符串分割，使用到了正则表达式，再倒序输出。

public String reverseWords(String s)
{
    String[] s_split = s.trim().split(" +");
    StringBuffer ans = new StringBuffer();

    for (int i = s_split.length - 1; i >= 1; i--) {
        ans.append(s_split[i] + " ");
    }
    ans.append(s_split[0]);

    return new String(ans);
}

242. 有效的字母异位词

难度：简单

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

示例 1:

输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

输入: s = "rat", t = "car"
输出: false

说明:
你可以假设字符串只包含小写字母。

进阶:
如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

把两个字符串排序，再判断是否相等。

public boolean isAnagram(String s, String t) {
    char[] c_s = s.toCharArray();
    char[] c_t = t.toCharArray();
    Arrays.sort(c_s);
    Arrays.sort(c_t);

    return Arrays.equals(c_s,c_t);
}

409. 最长回文串

难度：简单

给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。

在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。

注意:
假设字符串的长度不会超过 1010。

示例 1:

输入:
"abccccdd"

输出:
7

解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。

用一个数组记录每个字符出现的次数，偶数次的可以用来作为回文串。

如果最后得到的长度比字符串长度小，可以再加一位放在中间。

注意：char可以作为数组的索引

public int longestPalindrome(String s) {
    int[] count = new int[256];
    for (char c : s.toCharArray()) {
        count[c]++;
    }
    int longest = 0;
    for (int i : count) {
        longest += (i / 2) * 2;
    }
    if (longest < s.length()) {
        longest++;
    }
    return longest;
}

205. 同构字符串

难度：简单

给定两个字符串 s 和 t，判断它们是否是同构的。

如果 s 中的字符可以被替换得到 t ，那么这两个字符串是同构的。

所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。两个字符不能映射到同一个字符上，但字符可以映射自己本身。

示例 1:

输入: s = "egg", t = "add"
输出: true

示例 2:

输入: s = "foo", t = "bar"
输出: false

示例 3:

输入: s = "paper", t = "title"
输出: true

说明:
你可以假设 s 和 t 具有相同的长度。

维护一个数组，记录每个字符上次出现的位置，如果都能对上（两个字符串中的字符上次出现的位置一样），则说明是同构的。

public boolean isIsomorphic(String s, String t) {
    int[] preIndexOfS = new int[256];
    int[] preIndexOfT = new int[256];
    for(int i = 0; i < s.length(); i++){
        char sc = s.charAt(i);
        char tc = t.charAt(i);
        if(preIndexOfS[sc] != preIndexOfT[tc]){
            return false;
        }
        preIndexOfS[sc] = i + 1;
        preIndexOfT[tc] = i + 1;
    }
    return true;
}

647. 回文子串

难度：中等

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。

示例 1:

输入: "abc"
输出: 3
解释: 三个回文子串: "a", "b", "c".

示例 2:

输入: "aaa"
输出: 6
说明: 6个回文子串: "a", "a", "a", "aa", "aa", "aaa".

注意:

1. 输入的字符串长度不会超过1000。

对字符串的每个字符，使用扩展子串的方法计数，计数结果用一个全局变量保存。

扩展子串法：

使用双指针，一个往左，一个往右，只要不到头就继续往前走，每次挪一个字符，如果两个指针指的字符相等，就可以再走一步。

private int count = 0;
public int countSubstrings(String s) {
    for (int i = 0; i < s.length(); i++) {
        extendSubstring(s, i, i); // 奇数
        extendSubstring(s, i, i + 1);  // 偶数
    }
    return count;
}

private void extendSubstring (String s, int start, int end) {
    while (start >= 0 && end <= s.length() - 1 && s.charAt(start) == s.charAt(end)) {
        count++;
        start--;
        end++;
    }
}

9. 回文数

难度：简单

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

示例 1:

输入: 121
输出: true

示例 2:

输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例 3:

输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。

进阶:

你能不将整数转为字符串来解决这个问题吗？

如果一个整数小于0或者是10的整数倍，就肯定不是回文数。

使用一个int变量记录这个整数右半边的数（如果是奇数长度的，则包含正中间那一位）。

用取余除十的方法计算right，最后查看左边和右边的数是否相等，相等则是回文数。

public boolean isPalindrome(int x) {
    if (x == 0) {
        return true;
    }
    if (x < 0 || x % 10 == 0) {
        return false;
    }

    int right = 0;
    while (x > right) {
        right = x % 10 + right * 10;
        x /= 10;
    }
    return x == right || x == right / 10;
}

696. 计数二进制子串

难度：简单

给定一个字符串 s，计算具有相同数量0和1的非空(连续)子字符串的数量，并且这些子字符串中的所有0和所有1都是组合在一起的。

重复出现的子串要计算它们出现的次数。

示例 1 :

输入: "00110011"
输出: 6
解释: 有6个子串具有相同数量的连续1和0：“0011”，“01”，“1100”，“10”，“0011” 和 “01”。

请注意，一些重复出现的子串要计算它们出现的次数。
另外，“00110011”不是有效的子串，因为所有的0（和1）没有组合在一起。

示例 2 :

输入: "10101"
输出: 4
解释: 有4个子串：“10”，“01”，“10”，“01”，它们具有相同数量的连续1和0。

注意：

• s.length 在1到50,000之间。
• s 只包含“0”或“1”字符。

使用两个变量，cur记录当前有几个连续的0/1，pre记录上一个连续的0/1有几个。

每次比较前后两个字符串，如果相等，则cur数量+1，如果不等，则把cur的值赋给pre，他们俩的使命交接了，同时，cur变成1。

在每次移动索引的时候，如果能维持pre >= cur的状态，则结果计数器要+1。

public int countBinarySubstrings(String s) {
    int ans = 0, pre = 0, cur = 1;
    for (int i = 1; i < s.length(); i++) {
        if (s.charAt(i) == s.charAt(i - 1)) {
            cur++;
        } else {
            pre = cur;
            cur = 1;
        }
        if (pre >= cur) {
            ans++;
        }
    }
    return ans;
}