今天学习代码随想录新的一章--字符串，完成以下题目

344.反转字符串

这题要求输入：["h","e","l","l","o"] 输出：["o","l","l","e","h"]，而且题目中要求你不能再额外开辟空间，也就是不能再创建一个数组，用倒叙遍历原数组这种方式。我们只能对原数组进行操作，利用双指针法，一个在头一个在尾，交换就行。

541.反转字符串||

输入: s = "abcdefg", k = 2输出: "bacdfeg"

这题也是用双指针，关键就是要找明白哪个是start指针，哪个是end指针。题目要求从字符串开头算起, 每计数至 2k 个字符，就反转这 2k 个字符中的前 k 个字符。因此我们可以让for循环中的变量i为start，步长就是2*k，这次start是i，下次start就是i+2*k。end指针就是从i开始数k个数就行，就是end = i + k - 1（这时是从i所在元素开始的剩余元素数量大于k）。但是如果剩余元素不足k个时（也就是i +k-1 > s.length-1），end就是数组尾部索引，因此求end指针时要判断剩余元素和k的大小，取二者小值，之后交换就行。

class Solution {
    public String reverseStr(String s, int k) {
        //每次遍历字符串的步长 i += 2k
        char[] ch = s.toCharArray();
        for(int i = 0;i < ch.length;i += 2*k){
            //起始索引就在i处
            int start = i;
            //找终止索引
            //找的时候就就要判断剩下的元素够不够k个，比k大那end就正常指向start + k -1处，然后交换这k个元素。没有k大end就指向末尾，有几个就交换几个。
            int end = Math.min(ch.length - 1,start + k -1);
            //交换
            while(start < end){
                char temp = ch[start];
                ch[start] = ch[end];
                ch[end] = temp;
                start++;
                end--;
            }
        }

        return new String(ch);
    }
}

剑指Offer 05.替换空格

输入：s = "We are happy."输出："We%20are%20happy."

这题做到极致，是不需要创建额外空间，对原字符串操作就行。先对原数组进行扩容，然后再用双指针填充即可

1.创建一个StringBuilder，名字就叫sb，用来做扩容的

2.遍历s，遇到一个空格，sb就执行append(" "）,添加有两个空格的字符串，注意是两个，因为原来一个空格变成"%20"，多了两个位置存放字符，那额外再加两个空格就有三个空格了，补充了%20的大小。就比如原来s = " We are"，大小为6，扩容之后大小为8。

3.把sb转成字符串，再用字符串拼接完成s的扩容。s += sb.toString()

4.双指针法，一个指针left指向原s的尾部，例子中的y这个位置，另一个指针right指向扩容后数组尾部。然后把left对应的元素复制到right，遇到空格就要在right位置按顺序填写%20。

如果之后遇到填充数组的问题，都可以考虑先扩充数组，然后从后向前填充。如果从前向后填充，会让后面的元素都移动，这样时间复杂度就变成O(n²)了。

public String replaceSpace(String s) {
    if(s == null || s.length() == 0){
        return s;
    }
    //扩充空间，空格数量2倍
    StringBuilder str = new StringBuilder();
    for (int i = 0; i < s.length(); i++) {
        if(s.charAt(i) == ' '){
            str.append("  ");
        }
    }
    //若是没有空格直接返回
    if(str.length() == 0){
        return s;
    }
    //有空格情况 定义两个指针
    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 new String(chars);
}

151.翻转字符串里的单词

输入: "the sky is blue"输出: "blue is sky the"

输入: "  hello world!  "输出: "world! hello"

这题有点麻烦，分为三步，对应三个方法。

1.去除字符串多余空格

2.反转整个字符串

3.反转字符串里的每个单词

讲一下去除空格的细节，对一个字符串，先去除头部空格，再去除尾部空格，最后去除中间多余空格。用双指针法，头部指针用来去除头部空格，尾部指针去除尾部空格，最后遍历中间的，去除空格。

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++;
        }
        // System.out.println("ReverseWords.removeSpace returned: sb = [" + sb + "]");
        return sb;
    }

class Solution {
    public String reverseWords(String s) {
        //一共三个步骤
        //1.去除多余空格
        //2.反转整个s
        //3.反转每个单词
        String str = removeSpace(s);
        str = reverseString(str,0,str.length()-1);
        str = reverseWord(str);
        return str;

    }

    public  String reverseWord(String s){
        int start = 0;
        int end = 1;
        while(start < s.length()){
            while(end < s.length() && s.charAt(end) != ' '){
                end++;
            }
            s = reverseString(s,start,end-1);
            start = end+1;
            end = end+1;
        }


        return s;
    }
    public  String reverseString(String s,int start,int end){

        char[] ch = s.toCharArray();

        while(start < end){
            char temp = ch[start];
            ch[start] = ch[end];
            ch[end] = temp;
            start++;
            end--;
        }

        return new String(ch);
    }
    public  String 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){
            if(s.charAt(start) != ' ' || sb.charAt(sb.length() - 1) != ' ' ){
                sb.append(s.charAt(start));
            }
            start++;
        }

        return new String(sb);
    }

}

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

输入: s = "abcdefg", k = 2输出: "cdefgab"

这题我的做法是用到了替换空格这题中的思路，先扩充k个单元，然后用双指针复制，不难。

class Solution {
    public String reverseLeftWords(String s, int n) {
         //先扩张
        StringBuilder sb = new StringBuilder();
        for(int i = 0;i < n;i++){
            sb.append(" ");
        }

        //双指针

        int right = s.length();
        s += sb.toString();
        char[] ch = s.toCharArray();

        for(int left = 0;left < n;left++){
            ch[right] = ch[left];
            right++;
        }

        StringBuilder newSb = new StringBuilder();
        for(int i = n;i < ch.length;i++){
            newSb.append(ch[i]);
        }
        return new String(newSb);
    }
}

代码随想录中的做法是先反转前k个元素，再反转后面的元素，最后反转整个字符串，大家可以试试。