04.String（字符串）

1、反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。不要给另外的数组分配额外的空间，必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

    public static void reverseSwp(char[] s) {
        int l = 0;
        int r = s.length - 1;
        char tmp;
        while (l < r) {
            tmp = s[l];
            s[l] = s[r];
            s[r] = tmp;
            l++;
            r--;
        }
    }

    public void reverseXor(char[] s) {
        int l = 0;
        int r = s.length - 1;
        while (l < r) {
            s[l] ^= s[r];  //构造 a ^ b 的结果，并放在 a 中
            s[r] ^= s[l];  //将 a ^ b 这一结果再 ^ b ，存入b中，此时 b = a, a = a ^ b
            s[l] ^= s[r];  //a ^ b 的结果再 ^ a ，存入 a 中，此时 b = a, a = b 完成交换
            l++;
            r--;
        }
    }

2、反转字符串 II

给定一个字符串 s 和一个整数 k，从字符串开头算起, 每计数至 2k 个字符，就反转这 2k 个字符中的前 k 个字符。如果剩余字符少于 k 个，则将剩余字符全部反转。如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

示例:

输入: s = "abcdefg", k = 2
输出: "bacdfeg"

思路

在遍历字符串的过程中，只要让 i += (2 * k)，i 每次移动 2 * k 就可以了，然后判断是否需要有反转的区间。

    public static String reverseII(String s, int k) {
        char[] chars = s.toCharArray();
        int b;
        int e;
        // 每隔2k个反转前k个，尾数不够k个时候全部反转
        for (int i = 0; i < chars.length; i += 2 * k) {
            b = i;
            // 判断尾数够不够k个来取决end指针的位置
            e = Math.min(chars.length - 1, b + k - 1);
            // 用异或运算反转
            while (b < e) {
                chars[b] ^= chars[e];
                chars[e] ^= chars[b];
                chars[b] ^= chars[e];
                b++;
                e--;
            }
        }
        return String.valueOf(chars);
    }

3、替换数字

给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为 number。

示例：

输入: "a1b2c3"，输出: "anumberbnumbercnumber"。
输入: "a5b"，输出: "anumberb"

思路

首先扩充数组到每个数字字符替换成 "number" 之后的大小；
从后向前填充元素，避免了从前向后填充元素时，每次添加元素都要将添加元素之后的所有元素向后移动的问题。

    public static String replaceNumber(String s) {
        int length = s.length();
        for (int i = 0; i < s.length(); i++) {
            if (Character.isDigit(s.charAt(i))) {
                length += 5;
            }
        }
        char[] array = "number".toCharArray();
        char[] chars = new char[length];
        int j = length - 1;
        char c;
        for (int i = s.length() - 1; i >= 0; i--) {
            c = s.charAt(i);
            if (Character.isDigit(c)) {
                j -= array.length;
                System.arraycopy(array, 0, chars, j + 1, array.length);
            } else {
                chars[j--] = c;
            }
        }
        return String.valueOf(chars);
    }

4、翻转字符串里的单词

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

示例 1：

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

示例 2：

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

示例 3：

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

思路

移除多余空格
将整个字符串反转
将每个单词反转

给自己找麻烦不使用 trim()，split()，reverse()，StringBuilder 等工具方法和类，在一个数组中实现。

    public static String reverseWords(String s) {
        // 1. 移除多余空格，并将有效的字符串移动到数组起始位置
        char[] chars = s.toCharArray();
        int slow = 0;
        for (int fast = 0; fast < s.length(); fast++) {
            if (chars[fast] != ' ') { // 先用 fast 移除所有空格
                if (slow != 0) {
                    // 再用 slow 加空格，除第一个单词外，后面单词的开头要加空格
                    chars[slow++] = ' ';
                }
                while (fast < chars.length && chars[fast] != ' ') {
                    // fast 遇到空格或遍历到字符串末尾，就证明遍历完一个单词了
                    chars[slow++] = chars[fast++];
                }
            }
        }
        // 2. 反转字符串
        int l = 0;
        int r = slow - 1; // slow的值是字符串长度，所以反转时最后一个元素的下标要-1
        reverseChars(chars, l, r);
        // 3. 反转每个单词，遇到空格或达到指定长度则反转
        int b = 0;
        for (int e = 0; e <= slow; e++) {
            if (e == slow || chars[e] == ' ') { // 这里先判断等于字符串长度，避免可能出现的数组越界
                reverseChars(chars, b, e - 1);
                b = e + 1;
            }
        }
        return new String(chars, 0, slow);
    }

    private static void reverseChars(char[] chars, int l, int r) {
        while (l < r) {
            chars[l] ^= chars[r];
            chars[r] ^= chars[l];
            chars[l] ^= chars[r];
            l++;
            r--;
        }
    }

5、右旋字符串

字符串的右旋转操作是把字符串尾部的若干个字符转移到字符串的前面。给定一个字符串 s 和一个正整数 k，请编写一个函数，将字符串中的后面 k 个字符移到字符串的前面，实现字符串的右旋转操作。

例如，对于输入字符串 "abcdefg" 和整数 2，函数应该将其转换为 "fgabcde"。

思路

使用整体反转+局部反转，负负得正。

    public static String moveToRight(String s, int n) {
        char[] chars = s.toCharArray();
        reverseChars(chars, 0, chars.length - 1); // 整体反转
        reverseChars(chars, 0, n - 1); // 局部反转 [0, n)
        reverseChars(chars, n, chars.length - 1); // 局部反转 [n, chars.length)
        return String.valueOf(chars);
    }

    private static void reverseChars(char[] chars, int l, int r) {
        while (l < r) {
            chars[l] ^= chars[r];
            chars[r] ^= chars[l];
            chars[l] ^= chars[r];
            l++;
            r--;
        }
    }

6、 KMP

To be continued...

04.String（字符串）

1、 反转字符串

2、 反转字符串 II