字符串第一天，加油！

344.反轉(zhuǎn)字符串

解題思路：

設(shè)置兩個(gè)指針在字符串的首尾，分別交換指針指向的字符串元素即可
Tipp：
java中交換數(shù)值有兩種方法
- temp交換，常規(guī)，solution中的
- 位運(yùn)算交換(異或運(yùn)算)
可交換性：a^b=ba
可結(jié)合性：a^bc=(a^b)c=a^(bc)
自身進(jìn)行異或運(yùn)算值為零：a^a=0
與 0 異或時(shí)結(jié)果不變：a^0=a
實(shí)現(xiàn)：
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. 反轉(zhuǎn)字符串II

解法一：

運(yùn)用雙指針進(jìn)行翻轉(zhuǎn)
1.左指針的位置為每次間隔2k
1.需要判斷右指針的位置
·當(dāng) k<= 剩余字符串長(zhǎng)度 <= 2k時(shí)，右指針在i+k-1；
·當(dāng) 剩余字符串長(zhǎng)度 <k 時(shí)，右指針直接在字符串末尾，因?yàn)閷⑹Ｓ嗟淖址挤崔D(zhuǎn)

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時(shí)，右指針的點(diǎn)在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) {
                //位運(yùn)算實(shí)現(xiàn)翻轉(zhuǎn)函數(shù)
        while (left < right) {
            s[left] ^= s[right];
            s[right] ^= s[left];
            s[left] ^= s[right];
            left++;
            right--;
        }
    }
}
/*復(fù)雜度分析：
時(shí)間復(fù)雜度為O(n)，n為s長(zhǎng)度
空間復(fù)雜度為O(n)，因?yàn)閷⒆址D(zhuǎn)為了數(shù)組，變成了可以修改的字符串;java中String不可修改
*/

題目：劍指Offer 05.替換空格

解題思路：

依次讀取s中的字符，檢測(cè)是否為空格，如果是就添加%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();
    }
}

    /*
    時(shí)間復(fù)雜度為O(n)，n為字符串長(zhǎng)度
    空間復(fù)雜度為O(n)，n為原字符長(zhǎng)度+2*空格數(shù)量
    */

題目：劍指Offer58-II.左旋轉(zhuǎn)字符串

解題思路：雙指針

實(shí)現(xiàn)三次反轉(zhuǎn)，運(yùn)用自己寫(xiě)的reverse函數(shù)
1.先將0到n的字符翻轉(zhuǎn)
2.再將n+1到末尾的字符反轉(zhuǎn)
3.最后將整個(gè)字符翻轉(zhuǎn)
其中翻轉(zhuǎn)函數(shù)還是用雙指針

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--;       
        }
    }
}