字符串第一天，加油！

344.反转字符串

解题思路：

设置两个指针在字符串的首尾，分别交换指针指向的字符串元素即可
Tipp：
java中交换数值有两种方法
- temp交换，常规，solution中的
- 位运算交换(异或运算)
可交换性：a^b=ba
可结合性：a^bc=(a^b)c=a^(bc)
自身进行异或运算值为零：a^a=0
与 0 异或时结果不变：a^0=a
实现：
a ^=b;
b ^=a;
a ^=b;

class Solution {
    public void reverseString(char[] s) {
        int l = 0;
        int r = s.length - 1;
        
        char temp;
        while (l < r) {
            temp = s[l];
            s[l] = s[r];
            s[r] = temp;

            l++;
            r--;
        }
    }
}

541. 反转字符串II

解法一：

运用双指针进行翻转
1.左指针的位置为每次间隔2k
1.需要判断右指针的位置
·当 k<= 剩余字符串长度 <= 2k时，右指针在i+k-1；
·当 剩余字符串长度 <k 时，右指针直接在字符串末尾，因为将剩余的字符串都反转

class Solution {
    public String reverseStr(String s, int k) {
        int n = s.length();
        char[] arr = s.toCharArray();
        for (int i = 0; i < n; i += (2 * k)) {
            //如果剩余字符大于等于k，但是小于2k时，右指针的点在i+k-1上
            if (i + k <= n) {
                reverse(arr, i, (i+k)-1);
            } else {
                reverse(arr, i, n-1);
            }
        }
        // for (int i = 0; i < n; i += (2 * k)) {
        //     reverse(arr, i, Math.min(i + k, n) - 1);
        // }
        return new String(arr);

    }
    public void reverse(char[] s, int left, int right) {
                //位运算实现翻转函数
        while (left < right) {
            s[left] ^= s[right];
            s[right] ^= s[left];
            s[left] ^= s[right];
            left++;
            right--;
        }
    }
}
/*复杂度分析：
时间复杂度为O(n)，n为s长度
空间复杂度为O(n)，因为将字符串转为了数组，变成了可以修改的字符串;java中String不可修改
*/

题目：剑指Offer 05.替换空格

解题思路：

依次读取s中的字符，检测是否为空格，如果是就添加%20；不是就读原字符

class Solution {
    public String replaceSpace(String s) {
        StringBuilder res = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (c == ' ') {
                res.append("%20");
            } else {
                res.append(c);
            }
        }
        return res.toString();
    }
}

    /*
    时间复杂度为O(n)，n为字符串长度
    空间复杂度为O(n)，n为原字符长度+2*空格数量
    */

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

解题思路：双指针

实现三次反转，运用自己写的reverse函数
1.先将0到n的字符翻转
2.再将n+1到末尾的字符反转
3.最后将整个字符翻转
其中翻转函数还是用双指针

class Solution {
    public String reverseLeftWords(String s, int n) {
        StringBuilder res = new StringBuilder(s);
        reverseString(res, 0, n-1);
        reverseString(res, n, s.length()-1);
        return res.reverse().toString();

    }
    public void reverseString(StringBuilder res, int left, int right) {
        char temp;
        while (left < right) {
            temp = res.charAt(left);
            res.setCharAt(left, res.charAt(right));
            res.setCharAt(right, temp);
            left++;
            right--;       
        }
    }
}