当前位置：首页 > news >正文

算法：字符串part02: 151.翻转字符串里的单词 + 右旋字符串 + KMP算法28. 实现 strStr()

news 2025/8/3 11:02:50

151.翻转字符串里的单词

题目：https://leetcode.cn/problems/reverse-words-in-a-string/description/
文章讲解：https://programmercarl.com/0151.%E7%BF%BB%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2%E9%87%8C%E7%9A%84%E5%8D%95%E8%AF%8D.html
视频（这道题琐碎，建议先看视频）：https://www.bilibili.com/video/BV1uT41177fX/

思想

三步走：

（1）先去除多余空格（开头结尾空格+中间多余的空格）
（2）反转整个字符串；
（3）反转字符串中的所有单词

解题

class Solution {public String reverseWords(String s) {//（1）步骤一：去除不必要的空格（只保留单词中间的空格）char[] chars=s.toCharArray();chars=removeExtraSpace(chars);//（2）步骤二：反转整个字符串reverse(chars,0,chars.length-1);//（3）步骤三：反转每个单词chars=reverseEachWord(chars);return new String(chars);}public char[] removeExtraSpace(char[] chars){//用双指针的方法去除空格int slowIndex=0;for(int fastIndex=0;fastIndex<chars.length;fastIndex++){if(chars[fastIndex]!=' '){if(slowIndex!=0){chars[slowIndex++]=' ';}while(fastIndex<chars.length&&chars[fastIndex]!=' '){chars[slowIndex++]=chars[fastIndex++];}}}char[] newChar=new char[slowIndex];System.arraycopy(chars,0,newChar,0,slowIndex);return newChar;}public char[] reverse(char[] chars,int start,int end){while(start<end){char temp=chars[start];chars[start]=chars[end];chars[end]=temp;start++;end--;}return chars;}public char[] reverseEachWord(char[] chars){int start=0;for(int end=0;end<=chars.length;end++){if(end==chars.length||chars[end]==' '){reverse(chars,start,end-1);start=end+1;}}return chars;}
}////这里是参考答案，会更清晰，上面是我写的
/** 解法四：时间复杂度 O(n)* 参考卡哥 c++ 代码的三步骤：先移除多余空格，再将整个字符串反转，最后把单词逐个反转* 有别于解法一 ：没有用 StringBuilder  实现，而是对 String 的 char[] 数组操作来实现以上三个步骤*/
class Solution {//用 char[] 来实现 String 的 removeExtraSpaces，reverse 操作public String reverseWords(String s) {char[] chars = s.toCharArray();//1.去除首尾以及中间多余空格chars = removeExtraSpaces(chars);//2.整个字符串反转reverse(chars, 0, chars.length - 1);//3.单词反转reverseEachWord(chars);return new String(chars);}//1.用 快慢指针 去除首尾以及中间多余空格，可参考数组元素移除的题解public char[] removeExtraSpaces(char[] chars) {int slow = 0;for (int fast = 0; fast < chars.length; fast++) {//先用 fast 移除所有空格if (chars[fast] != ' ') {//在用 slow 加空格。 除第一个单词外，单词末尾要加空格if (slow != 0)chars[slow++] = ' ';//fast 遇到空格或遍历到字符串末尾，就证明遍历完一个单词了while (fast < chars.length && chars[fast] != ' ')chars[slow++] = chars[fast++];}}//相当于 c++ 里的 resize()char[] newChars = new char[slow];System.arraycopy(chars, 0, newChars, 0, slow); return newChars;}//双指针实现指定范围内字符串反转，可参考字符串反转题解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;}}}
}

总结

参照思想，一些琐碎的小细节别写错（比如判断的是下标还是下标对应的值）

右旋字符串

题目：https://kamacoder.com/problempage.php?pid=1065
文章讲解：https://programmercarl.com/kamacoder/0055.%E5%8F%B3%E6%97%8B%E5%AD%97%E7%AC%A6%E4%B8%B2.html
（第一次接触可能想不到这个方法，建议直接看讲解，其实思路不难，只是第一次很难想）

思想

右旋和左旋的思路一致，都是把最前面的n个元素挪至最后，或者把最后的n个元素挪至最前面
相当于先逆转整个字符数组，然后对由旋转部位划分的两个子串逆转

解题

import java.util.Scanner;class Main{public static void main(String[] args){//拿到初始值Scanner in=new Scanner(System.in);int n=Integer.parseInt(in.nextLine());String s=in.nextLine();char[] chars=s.toCharArray();//先反转整个字符数组chars=reverse(chars,0,chars.length-1);//再分别反转两个子串//(1)反转前n个chars=reverse(chars,0,n-1);//(2)反转后面的length-n个chars=reverse(chars,n,chars.length-1);System.out.println(new String(chars));}public static char[] reverse(char[] chars,int start,int end){while(start<end){char temp=chars[start];chars[start]=chars[end];chars[end]=temp;start++;end--;}return chars;}
}////这里是参考答案，会更清晰，上面是我写的
// 版本一
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = Integer.parseInt(in.nextLine());String s = in.nextLine();int len = s.length();  //获取字符串长度char[] chars = s.toCharArray();reverseString(chars, 0, len - 1);  //反转整个字符串reverseString(chars, 0, n - 1);  //反转前一段字符串，此时的字符串首尾尾是0,n - 1reverseString(chars, n, len - 1);  //反转后一段字符串，此时的字符串首尾尾是n,len - 1System.out.println(chars);}public static void reverseString(char[] ch, int start, int end) {//异或法反转字符串，参照题目 344.反转字符串的解释while (start < end) {ch[start] ^= ch[end];ch[end] ^= ch[start];ch[start] ^= ch[end];start++;end--;}}
}

总结

参照思想

KMP算法28. 实现 strStr()

题目：https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/description/
文章讲解：https://programmercarl.com/0028.%E5%AE%9E%E7%8E%B0strStr.html

思想

暴力解法可以用双层for，但是这里要注意的是，边界条件和代码逻辑容易出错，需要多练几遍记熟
第二种解法就是KMP（命名是三位发明者的首字母），不是很好理解，但有些大厂面试考过；

解法

//暴力解法
class Solution {public int strStr(String haystack, String needle) {if (needle == null || needle.isEmpty()) {return 0;}int n = haystack.length();int m = needle.length();if (n < m) {return -1;}for (int i = 0; i <= n - m; i++) {  // 外层循环：遍历所有可能的起始位置boolean found = true;for (int j = 0; j < m; j++) {   // 内层循环：检查是否完全匹配if (haystack.charAt(i + j) != needle.charAt(j)) {found = false;break;}}if (found) {  // 如果完全匹配，返回当前起始位置 ireturn i;}}return -1;  // 未找到匹配}
}//KMP算法