二、541. 反转字符串II

力扣

思路：在遍历字符串的过程中，只要让 i += (2 * k)，i 每次移动 2 * k 就可以了，然后判断是否需要有反转的区间。因为要找的也就是每2 * k 区间的起点，这样写，程序会高效很多。

   所以当需要固定规律一段一段去处理字符串的时候，要想想在在for循环的表达式上做做文章。

class Solution {
    public  String reverseStr(String s, int k) {
        for (int i = 0; i < s.length(); i += 2*k) {
            // 1. 每隔 2k 个字符的前 k 个字符进行反转
            // 2. 剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符
            if (i + k <= s.length()) {
                s = reverse(s, i, i + k - 1);
                continue;
            }else {
                // 3. 剩余字符少于 k 个，则将剩余字符全部反转。
                s = reverse(s, i, s.length() - 1);
            }
        }
        return s;
    }
    private  String reverse(String s, int start, int end) {
        char[] str = s.toCharArray();
        //System.out.println("str1=" + str.toString());
        for (int i = start, j = end; i < j; i++, j--) {
            char temp = str[i];
            str[i] = str[j];
            str[j] = temp;
        }
        return String.valueOf(str);
    }
}

三、剑指Offer 05.替换空格

力扣

思路1: 使用StringBuilder，遇到空格就把空格换成“%20”。

class Solution {
    public String replaceSpace(String s) {
        if (s == null) {
            return null;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) != ' ') {
                sb.append(s.charAt(i));
            }else {
                sb.append("%20");
            }
        }
        return sb.toString();
    }
}

思路2:首先扩充数组到每个空格替换成"%20"之后的大小。然后从后向前替换空格，也就是双指针法，过程如下：i指向新长度的末尾，j指向旧长度的末尾。

从前向后填充就是O(n^2)的算法了，因为每次添加元素都要将添加元素之后的所有元素向后移动。

其实很多数组填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作。

这么做有两个好处：

1. 不用申请新数组。
2. 从后向前填充元素，避免了从前先后填充元素要来的 每次添加元素都要将添加元素之后的所有元素向后移动。

tips:将字符数组变成字符串的方法：1.new String(chars)   2.String.valueOf(chars) .

class Solution {
    public String replaceSpace(String s) {
        if (s.length() == 0 || s == null) {
            return s;
        }
        StringBuilder str = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if(s.charAt(i) == ' '){
                str.append("  ");
            }
        }
        int left = s.length() - 1;//左指针：指向原始字符串最后一个位置
        s += str.toString();
        int right = s.length()-1;//右指针：指向扩展字符串的最后一个位置
        char[] chars = s.toCharArray();
        while (left >= 0) {
            if (chars[left] == ' ') {
                chars[right--] = '0';
                chars[right--] = '2';
                chars[right] = '%';
            }else {
                chars[right] = chars[left];
            }
            left--;
            right--;
        }
        return String.valueOf(chars);
    }
}

四、151.翻转字符串里的单词

力扣

思路：

class Solution {
     /**
     * 不使用Java内置方法实现
     * 1.去除首尾以及中间多余空格
     * 2.反转整个字符串
     * 3.反转各个单词
     */
    public String reverseWords(String s) {
         // 1.去除首尾以及中间多余空格
        StringBuilder sb = removeSpace(s);
        // 2.反转整个字符串
        reverseString(sb, 0, sb.length() - 1);
        // 3.反转各个单词
        reverseEachWord(sb);
        return sb.toString();
    }
    private StringBuilder removeSpace(String s) {
        int start = 0;
        int end = s.length() - 1;
        // 去掉字符串前面的空格
        while (s.charAt(start) == ' ') start++;
        while (s.charAt(end) == ' ') end--;
        StringBuilder sb = new StringBuilder();
        // 去掉字符串中间部分的冗余空格
        while (start <= end) {
            char c =s.charAt(start);
            if(c != ' ' || sb.charAt(sb.length() - 1) != ' ') {
                sb.append(c);
            }
            start++;
        }
        return sb;
    }
    /**
     * 反转字符串指定区间[start, end]的字符
     */
    private void reverseString(StringBuilder sb, int start, int end) {
         while (start < end) {
             char temp = sb.charAt(start);
             sb.setCharAt(start, sb.charAt(end));
             sb.setCharAt(end,temp);
             start++;
             end--;
         }
     }
     /**
     * 反转各个单词
     */
     private void reverseEachWord(StringBuilder sb) {
         int start = 0;
         int end = 1;//用来寻找单词的区间
         int n = sb.length();
         while (start < n) {
             while (end < n && sb.charAt(end) != ' ') {//空格前为一个完整单词
                 end++;
             }
             reverseString(sb, start, end - 1);
             start = end + 1;
             end = start + 1;
         }
     }
}

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

力扣

思路1：使用额外的空间很容易写出来，StringBuilder。

思路2：不使用额外的空间，1.反转区间为前n的子串 2.反转区间为n到末尾的子串 3.反转整个字符串。

class Solution {
    public String reverseLeftWords(String s, int n) {
        int len=s.length();
        StringBuilder sb=new StringBuilder(s);
        reverseString(sb,0,n-1);
        reverseString(sb,n,len-1);
        return sb.reverse().toString();
    }
    private void reverseString(StringBuilder sb, int start, int end) {
        while (start < end) {
            char temp = sb.charAt(start);
            sb.setCharAt(start, sb.charAt(end));
            sb.setCharAt(end, temp);
            start++;
            end--;
        }
    }
}

六、总结

在这篇文章344.反转字符串 (opens new window)，第一次讲到反转一个字符串应该怎么做，使用了双指针法。

然后发现541. 反转字符串II (opens new window)，这里开始给反转加上了一些条件，当需要固定规律一段一段去处理字符串的时候，要想想在在for循环的表达式上做做文章。

后来在151.翻转字符串里的单词 (opens new window)中，要对一句话里的单词顺序进行反转，发现先整体反转再局部反转 是一个很妙的思路。

最后再讲到本题，本题则是先局部反转再 整体反转，与151.翻转字符串里的单词 (opens new window)类似，但是也是一种新的思路。