代码随想录算法训练营第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算法都只看了原理和代码,因为这几天生病没有动手敲,等身体好点之后补回来


字符串总结

文章讲解


双指针回顾

文章讲解

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容