反轉(zhuǎn)字符串

題目鏈接

https://programmercarl.com/0344.%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2.html

思路

雙指針法，左右同時移動

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

反轉(zhuǎn)字符串II

題目鏈接

https://programmercarl.com/0541.%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2II.html

思路

每隔2k交換前k個字符，重點在于如何處理最后一段字符串的交換

     public String reverseStr(String s, int k) {
    char[] str = s.toCharArray();
    for(int i = 0; i < s.length();i = i +2*k) {
        int l = i;
        int r = Math.min(i + k -1,s.length() - 1);
        while(l < r ) {
            char tmp = str[l];
    str[l] = str[r];
    str[r] = tmp;
    l++;
    r--;
        }
    }
    return new String(str);
}

替換空格

題目鏈接

https://programmercarl.com/%E5%89%91%E6%8C%87Offer05.%E6%9B%BF%E6%8D%A2%E7%A9%BA%E6%A0%BC.html

思路

從后往前遍歷

    public String replaceSpace(String s) {
    char[] a = s.toCharArray();
    StringBuilder str = new StringBuilder();
    for(int i = 0;i< s.length() ;i++) {
        if(a[i] == ' ') {
            str.append("%20");
        } else {
            str.append(a[i]);
        }
    }
    return str.toString();
}

翻轉(zhuǎn)字符串單詞

題目鏈接

https://programmercarl.com/0151.%E7%BF%BB%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2%E9%87%8C%E7%9A%84%E5%8D%95%E8%AF%8D.html

思路

1、去掉空格，雙指針法
2、翻轉(zhuǎn)整個字符串
3、翻轉(zhuǎn)單詞

    public String reverseWords(String s) {
    char[] res = removeExtraSpaces(s.toCharArray());
    reverse(res, 0, res.length - 1);
    reverseEachWord(res);
    return new String(res);

}

private void reverseEachWord(char[] res) {
    int start = 0;
    for(int i =0; i <= res.length;i++) {
        if(  i == res.length || res[i] == ' ') {
            reverse(res, start, i - 1);
            start = i + 1;
        }
    }
}

public void reverse(char[] chars, int left, int right) {
    if (right >= chars.length) {
        System.out.println("set a wrong right");
        return;
    }
    while (left < right) {
        chars[left] ^= chars[right];
        chars[right] ^= chars[left];
        chars[left] ^= chars[right];
        left++;
        right--;
    }
}
    public char[] removeExtraSpaces(char[] res) {
    int l = 0,f = 0;
    while(f < res.length) {
        if(res[f] != ' ') {
            if(l != 0) {
                res[l++] = ' ';
            }
            while(f < res.length && res[f] != ' ') {
                res[l++] = res[f++];
            }
        }
        f++;
    }
    char[] newChars = new char[l];
    System.arraycopy(res, 0, newChars, 0, l);
    return newChars;
}

左旋轉(zhuǎn)字符串

題目鏈接

https://programmercarl.com/%E5%89%91%E6%8C%87Offer58-II.%E5%B7%A6%E6%97%8B%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2.html

思路

1、局部旋轉(zhuǎn)
2、整體旋轉(zhuǎn)

    public String reverseLeftWords(String s, int n) {
    char[] res = s.toCharArray();
    int l = 0;
    for(int i = n -1;i>l ;i--) {
        res[i] ^= res[l];
        res[l] ^= res[i];
        res[i]^= res[l];
        l++;
    }
    int h = s.length() - 1;
    for(int i = n ;h > i ;i++) {
        res[i] ^= res[h];
        res[h] ^= res[i];
        res[i]^= res[h];
        h--;
    }
     h = s.length() - 1;
    for(int i = 0 ;h > i ;i++) {
        res[i] ^= res[h];
        res[h] ^= res[i];
        res[i]^= res[h];
        h--;
    }
    
    return new String(res);
}