344.反转字符串

对字符串的基本操作。双指针一个指头一个指尾，交换后向中间移动即可。对于考察基本操作的题目，不要使用库函数。

交换操作，如果需要自己实现，有两种办法，一是使用临时变量，二是异或运算。使用临时变量的办法很常见，不额外贴代码。

异或运算的四种可能情况为：0 ^ 0 = 0, 0 ^ 1 = 1, 1 ^ 0 = 1, 1 ^ 1 = 0 。并且，异或满足交换律，因此 a ^ b ^ a = a ^ a ^ b = b。根据运算规则和交换律，写出使用异或运算交换变量的算法也就不难了。

Char a = 'a';
Char b = 'b';

a = a ^ b;
b = a ^ b;  // 此时 b = a ^ b ^ b = a
a = a ^ b;  // 此时 a = a ^ b ^ a = b

交换字符串的代码如下：

class Solution {
    public void reverseString(char[] s) {
        int left = 0;
        int right = s.length - 1;
        while(left < right) {
            char tmp = s[left];
            s[left] = s[right];
            s[right] = tmp;
            left++;
            right--;
        }
    }
}

541. 反转字符串II

上一个题目的拓展，增加对区间控制的考察。既然题目要求每 2k 个字符反转前 k 个字符，剩余字符不足 k 个时全部反转，那么在遍历时只需要让指针每次增加 2k 再进行判断即可。代码如下：

class Solution {
    public String reverseStr(String s, int k) {
        char[] ch = s.toCharArray();

        for (int i = 0; i < s.length(); i += 2 * k) {
            if (i + k > s.length()) {
                reverse(ch, i, s.length() - 1);
            } else {
                reverse(ch, i, i + k - 1);
            }
        }
        return new String(ch);
    }

    private void reverse (char[] ch, int left, int right) {  // 与题目主方法没有太大强关联性的方法可以单独拎出来另起一个方法，代码会更易读
        while (left <= right) {
            char c = ch[left];
            ch[left] = ch[right];
            ch[right] = c;
            left++;
            right--;
        }

    }
}

剑指Offer 05.替换空格

两种写法，其一是直接替换，其二是双指针。

直接替换就是遍历字符串，遇到空格直接替换成“%20”即可。

双指针法则需要先统计原字符串中的空格数，然后申请一个长度为原字符串长度 + 空格数量 * 2的新数组（每个空格被替换掉之后长度会相比于原先大2）。之后，使用一个指针指向原字符串的结尾，另一个指针指向新数组的结尾，同时向前移动，当指向原字符串的指针指向了空格时，就向新数组内添加“%20”。指向两者结尾的原因是，如果从开始向结尾进行填充，每进行一次填充，都需要移动数组内在这个元素之后的所有元素，导致时间复杂度升高，而从后向前填充只会对原来位置上的元素产生影响，不会升高时间复杂度。

由于Java的字符串不可更改，因此即使是双指针法也需要额外申请一整个数组的空间，降低空间复杂度的作用有限。

class Solution {
    public String replaceSpace(String s) {
        if (s.length() == 0 || s == null) return s;

        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == ' ') {
                count++;
            }
        }
        if (count == 0) return s;

        char[] result = new char[s.length() + count * 2];
        int left = s.length() - 1;
        int right = result.length - 1;
        for (; left >= 0; left--) {
            if (s.charAt(left) == ' ') {
                result[right--] = '0';
                result[right--] = '2';
                result[right--] = '%';
            } else {
                result[right--] = s.charAt(left);
            }
        }
        return new String(result);
    }
}

151.翻转字符串里的单词

综合考察字符串操作的题目。我选择兔子掉。

翻转的操作可以分解为以下三个步骤：

1. 删除字符串里所有多余的空格
2. 翻转整个字符串
3. 翻转每个单词

其中 2 和 3 本质上都是翻转字符串。
代码如下：

class Solution {
    public String reverseWords(String s) {
        StringBuilder s1 = deleteSpace(s);
        reverse(s1, 0, s1.length() - 1);
        reverseEachWord(s1);
        return s1.toString();
    }

    private StringBuilder deleteSpace(String s) {
        StringBuilder s1 = new StringBuilder();
        int left = 0;
        int right = s.length() - 1;
        while (s.charAt(left) == ' ') left++;
        while (s.charAt(right) == ' ') right--;
        while (left <= right) {
            if (s.charAt(left) != ' ' || s1.charAt(s1.length() - 1) != ' ') {
                s1.append(s.charAt(left));
            }
            left++;
        }
        return s1;
    }

    private void reverse(StringBuilder s1, int left, int right) {
        while (left < right) {
            char tmp = s1.charAt(left);
            s1.setCharAt(left, s1.charAt(right));
            s1.setCharAt(right, tmp);
            left++;
            right--;
        }
    }

    private void reverseEachWord(StringBuilder s1) {
        int left = 0;
        int right = 1;
        while (left < s1.length()) {
            while (right < s1.length() && s1.charAt(right) != ' ') {
                right++;
            }
            reverse(s1, left, right - 1);
            left = right + 1;
            right = left + 1;
        }
    }
}

剑指Offer58-II.左旋转字符串

最直观的办法就是先遍历后半截再遍历前半截，一点点加在字符串的结尾。

但是，本题也可以使用翻转字符串的方法完成。具体而言： 1. 分别翻转两个部分的字符串。 2. 翻转整个字符串。

似曾相识燕归来是吧。

代码如下：

class Solution {
    public String reverseLeftWords(String s, int n) {
        char[] ch = s.toCharArray();
        reverse(ch, 0, n - 1);
        reverse(ch, n, ch.length - 1);
        reverse(ch, 0, ch.length - 1);

        return new String(ch);
    }

    private void reverse(char[] ch, int left, int right) {
        while (left < right) {
            ch[left] ^= ch[right];
            ch[right] ^= ch[left];
            ch[left] ^= ch[right];
            left++;
            right--;
        }
    }
}

谁看了不说一句优雅。