代码随想录算法训练营第9天 | 151.翻转字符串里的单词、卡码网：55.右旋转字符串、28. 实现 strStr()、459.重复的子字符串、字符串总结、双指针回顾

之前只计算了做题的天数，今天改成和训练营的统计方式一致，所以是day9

151.翻转字符串里的单词

解题思路：
移除多余空格 -- 快慢指针
反转字符串 -- 双指针
反转单词

class Solution {
    public String reverseWords(String s) {
        // 用 char[] 来实现 String 的 removeExtraSpaces，reverse 操作
        char[] chars = s.toCharArray();
        // 1. 去除首尾及中间多余空格
        chars = removeExtraSpace(chars);
        // 2. 整个字符串反转
        reverse(chars, 0, chars.length - 1);
        // 3. 单词反转
        reverseEachWord(chars);
        return new String(chars);
    }

    // 1. 用快慢指针去除首尾以及中间多余空格
    public char[] removeExtraSpace(char[] chars) {
        int slow = 0;
        for (int fast = 0; fast < chars.length; fast++) {
            // 用 fast 移除空格
            if (chars[fast] != ' ') {
                // 除了第一个单词，其他都要在末尾加空格
                if (slow != 0) {
                    chars[slow++] = ' ';
                }
                while (fast < chars.length && chars[fast] != ' ') {
                    chars[slow++] = chars[fast++];
                }
            }
        }
        char[] newChars = new char[slow];
        System.arraycopy(chars, 0, newChars, 0, slow);
        return newChars;
    }

    // 2. 双指针实现指定范围内字符串反转，可参考字符串反转题解
    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--;
        }
    }

    // 3. 单词反转
    public void reverseEachWord(char[] chars) {
        int start = 0;
        // end <= s.length() 这里的 = ，是为了让 end 永远指向单词末尾后一个位置，这样 reverse 的实参更好设置
        for (int end = 0; end <= chars.length; end++) {
            // end 每次到单词末尾后的空格或串尾，开始反转单词
            if (end == chars.length || chars[end] == ' ') {
                reverse(chars, start, end - 1);
                start = end + 1;
            }
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String s = "  the sky is blue  ";
        System.out.println(solution.reverseWords(s)); // 输出 "blue is sky the"
    }
}

解法1中的StringBuilder不是很熟悉，二刷的时候可以看一下

卡码网：55.右旋转字符串

题目链接/文章讲解

解题思路

整体字母翻转
再反转两段子字符串

import java.util.Scanner;

import java.util.Scanner;

public class Main{
    public static void main (String[] args) {
        Scanner in = new Scanner(System.in);
        int k = Integer.parseInt(in.nextLine());
        String s = in.nextLine();
        
        int len = s.length();
        char[] chars = s.toCharArray();
        reverseString(chars, 0, len - 1);  //反转整个字符串
        reverseString(chars, 0, k - 1);  //反转前一段字符串，此时的字符串首尾尾是0,n - 1
        reverseString(chars, k, len - 1);  //反转后一段字符串，此时的字符串首尾尾是n,len - 1
        
        System.out.println(new String(chars));
    }
    
    public static void reverseString(char[] ch, int start, int end) {
        while(start < end){
            ch[start] ^= ch[end];
            ch[end] ^= ch[start];
            ch[start] ^= ch[end];
            start++;
            end--;
        }
    }
}

复习一下基础：
按位异或运算符（^）
按位异或运算符对二进制位执行异或操作。它遵循以下规则：
如果两个位相同，结果是0。
如果两个位不同，结果是1。

微信图片_20240616195138.jpg

28. 实现 strStr() （本题可以跳过）

题目链接/文章讲解/视频讲解

其实概念是看这个视频明白的

459.重复的子字符串（本题可以跳过）

题目链接/文章讲解/视频讲解

本题算是KMP算法的一个应用，不过对KMP了解不够熟练的话，理解本题就难很多。
我的建议是 KMP和本题，一刷的时候，可以适当放过，了解怎么回事就行，二刷的时候再来硬啃

kmp算法都只看了原理和代码，因为这几天生病没有动手敲，等身体好点之后补回来

字符串总结

文章讲解

双指针回顾