本文是每天跟着代码随想录刷题时做的笔记，用来总结与复习。

目录

344.反转字符串

541.反转字符串Ⅱ

剑指offer 05.替换空格

151.反转字符串里的单词

剑指offer 58-Ⅱ.左旋转字符串

28.实现strStr()

459.重复的子字符串

今日总结

344.反转字符串

题目链接：344. 反转字符串 - 力扣（LeetCode） (leetcode-cn.com)

思路：思路很简单，就是一个双指针加元素交换

 public void reverseString(char[] s) {
        int left = 0;
        int right = s.length - 1;
        while (left < right){
            char temp = s[left];
            s[left++] = s[right];
            s[right--] = temp;
        }
    }

541.反转字符串Ⅱ

题目链接：541. 反转字符串 II - 力扣（LeetCode） (leetcode-cn.com)

思路：在字符串长度范围内反转 0 + (2 * k) * i ~ (k - 1) + (2 * k) * i 下标的字符串，i 取值为 0，1，2，3.....，其中注意判断超出字符串长度的情况即可。

public String reverseStr(String s, int k) {
        char[] chars = s.toCharArray();
        int left = 0;
        int right = left + k - 1;
        if (right >= chars.length){
            right = chars.length - 1;
        }
        while (right < chars.length){
            int fLeft = left;
            int fRight = right;
            while (fLeft < fRight){
                char temp = chars[fLeft];
                chars[fLeft++] = chars[fRight];
                chars[fRight--] = temp;
            }
            left += 2 * k;
            right += 2 * k;
            if (left >= chars.length){
                break;
            }
            if (right >= chars.length){
                right = chars.length - 1;
            }
        }

        return new String(chars);
    }

剑指offer 05.替换空格

题目链接：剑指 Offer 05. 替换空格 - 力扣（LeetCode） (leetcode-cn.com)

思路：

①：直接使用 String 中的 replace 方法

    public String replaceSpace(String s) {
        String s1 = s.replace(" ", "%20");
        return s1;
    }

②：不使用库函数的解法，使用 StringBuilder 来进行字符串的拼接，提高速度

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

③：正规解法：先将字符串长度扩充到替换后的长度，这里要使用 StringBuilder 来进行扩充，因为 String 是不可变长的。设置两个指针，一个指向扩充前字符串末尾 (bf) ，一个指向扩充后的字符串末尾 (af) ，使用 bf 由前往后遍历字符串，若查找到空格，则使用 af 存入 "%20"，若没有查找到空格，则使用 af 存入 bf 对应字符

public String replaceSpace(String s){
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == ' '){
                count++;
            }
        }
        StringBuilder stringBuilder = new StringBuilder(s);
        for (int i = 0; i < count; i++) {
            stringBuilder.append("  ");
        }
        String str = stringBuilder.toString();
        char[] chars = str.toCharArray();
        int bf = s.length() - 1;
        int af = stringBuilder.length() - 1;
        while (bf >= 0){
            if (chars[bf] == ' '){
                chars[af--] = '0';
                chars[af--] = '2';
                chars[af--] = '%';
                bf--;
            }else {
                chars[af--] = chars[bf--];
            }
        }
        return new String(chars);
    }

151.反转字符串里的单词

题目链接：151. 翻转字符串里的单词 - 力扣（LeetCode） (leetcode-cn.com)

思路：

①：使用 String 中的 split 函数来获取每一个单词，在将单词进行拼接

public String reverseWords(String s) {
        String[] s1 = s.split(" ");
        StringBuilder str = new StringBuilder();
        int flag = 0;
        while (s1[flag].equals("")){
            flag++;
        }
        for (int i = s1.length - 1;  i > flag; i--) {
            if (!s1[i].equals("")){
                str.append(s1[i]);
                str.append(" ");
            }
        }
        str.append(s1[flag]);
        return str.toString();
    }

②：不使用库函数：先去除字符串头尾的空格，再将字符串反序并处理中间空格，如下

原字符串：

处理完后的字符串：  

最后再通过空格作为标志获取每个单词，将每个单词反转即可

public String reverseWords(String s) {
        char[] chars = s.toCharArray();
        int left = 0;
        int right = chars.length - 1;
        StringBuilder newStr = new StringBuilder();
        //去除头尾的空格
        while (left <= right){
            if (chars[left] == ' '){
                left++;
            }
            if (chars[right] == ' '){
                right--;
            }
            if (chars[left] != ' ' && chars[right] != ' '){
                break;
            }
        }
        //将字符串反序，并处理中间空格
        int bfRight = right - 1;
        while (right > left){
            if (chars[right] != ' ' || (chars[right] == ' ' && chars[bfRight] != ' ')){
                newStr.append(chars[right]);
            }
            right--;
            bfRight--;
        }
        newStr.append(chars[left]);
        getAndReverse(newStr);
        return newStr.toString();
    }
    //得到每个单词并将其反转
    public void getAndReverse(StringBuilder stringBuilder){
        int head = 0;
        int end = 0;
        while (end < stringBuilder.length()){
            if (stringBuilder.charAt(end) == ' '){
                reverse(stringBuilder, head, end - 1);
                head = end + 1;
            }
            end++;
        }
        reverse(stringBuilder, head, end - 1);
    }
    //反转每个单词
    public void reverse(StringBuilder stringBuilder, int head, int end){
        while (head < end){
            char temp = stringBuilder.charAt(head);
            stringBuilder.setCharAt(head, stringBuilder.charAt(end));
            stringBuilder.setCharAt(end, temp);
            head++;
            end--;
        }
    }

剑指offer 58-Ⅱ.左旋转字符串

题目链接：剑指 Offer 58 - II. 左旋转字符串 - 力扣（LeetCode） (leetcode-cn.com)

思路：

①：截取对应子串进行拼接

public String reverseLeftWords(String s, int n){
        StringBuilder ansStr = new StringBuilder();
        ansStr.append(s.substring(n, s.length()));
        ansStr.append(s.substring(0, n));
        return ansStr.toString();
    }

②：先反转整个字符串，再反转对应的对应子串

 public String reverseLeftWords(String s, int n){
        StringBuilder ansStr = new StringBuilder(s);
        int length = ansStr.length();
        reverse(ansStr, 0, length - 1);
        reverse(ansStr, 0, length - n - 1);
        reverse(ansStr, length - n, length - 1);
        return ansStr.toString();
    }
    public void reverse(StringBuilder stringBuilder, int head, int end){
        while (head < end){
            char temp = stringBuilder.charAt(head);
            stringBuilder.setCharAt(head, stringBuilder.charAt(end));
            stringBuilder.setCharAt(end, temp);
            head++;
            end--;
        }
    }

28.实现strStr()

题目链接：28. 实现 strStr() - 力扣（LeetCode） (leetcode-cn.com)

思路：

①：Horspool算法：设置一个移动表，设置规则如下图所示，根据匹配不成功时 haystack 字符串与 needle 字符串末尾对应的字符 c 的不同情况来对照移动表进行移动。

public int strStr(String haystack, String needle) {
        if (needle.length() == 0){
            return 0;
        }
        Map<Character, Integer> move = new HashMap<>();
        int flag = needle.length() - 1;
        int count = 0;
        if (needle.length() > 1){
            while (flag > 0){
                flag--;
                count++;
                if (!move.containsKey(needle.charAt(flag))){
                    move.put(needle.charAt(flag), count);
                }
            }
        }
        int hayPo = needle.length() - 1;
        while (hayPo < haystack.length()){
            int nePo = needle.length() - 1;
            int moveHayPo = hayPo;
            while (needle.charAt(nePo) == haystack.charAt(moveHayPo)){
                nePo--;
                moveHayPo--;
                if (nePo < 0){
                    return moveHayPo + 1;
                }
            }
            if (move.containsKey(haystack.charAt(hayPo))){
                hayPo += move.get(haystack.charAt(hayPo));
            }else {
                hayPo += needle.length();
            }
        }
        return -1;
    }

②：KMP 算法：直接学习卡哥的视频：

帮你把KMP算法学个通透！（理论篇）哔哩哔哩bilibili

帮你把KMP算法学个通透！（求next数组代码篇）哔哩哔哩bilibili

public int strStr(String haystack, String needle) {
        if (needle.length() == 0){
            return 0;
        }
        int[] next = new int[needle.length()];
        next[0] = 0;
        int j = 0;
        for (int i = 1; i < needle.length(); i++){
            while (j > 0 && needle.charAt(j) != needle.charAt(i)){
                j = next[j - 1];
                
            }
            if (needle.charAt(j) == needle.charAt(i)){
                j++;
            }
            next[i] = j;
        }
        int needPo = 0;
        for (int i = 0; i < haystack.length(); i++) {
            while (needPo > 0 && needle.charAt(needPo) != haystack.charAt(i))
                needPo = next[needPo - 1];
            if (needle.charAt(needPo) == haystack.charAt(i))
                needPo++;
            if (needPo == needle.length())
                return i - needle.length() + 1;
        }
        return -1;
    }

459.重复的子字符串

题目链接：459. 重复的子字符串 - 力扣（LeetCode） (leetcode-cn.com)

思路：同样使用 kmp 算法，通过分析 next 数组可以发现，如果用字符串的长度减去最长公共前后缀可以整除字符串的长度，那么则表示该字符串符合题意（当然是看的题解啦