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

代码随想录算法训练营第 9 天（字符串2）| 151.翻转字符串里的单词卡码网55.右旋转字符串 KMP（跳过）总结

article 2025/1/17 18:41:34

一、151.翻转字符串里的单词

题目：https://leetcode.cn/problems/reverse-words-in-a-string/

视频：https://www.bilibili.com/video/BV1uT41177fX

讲解：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

两次反转：第一次把字符串中所有字符都反转，第二次把内部每个单词反转

其中删除多余空格的思路：不是碰到多余的空格就删除，而是写新字符串的时候，每新遇到一个单词的时候，在前面加一个空格（视频思路）

| 以下代码的思路：

①先删除首尾以及单词之间多余的空格，②然后把整个字符串反转，③然后再把每个单词反转

class Solution {
    public String reverseWords(String s) {
        StringBuilder sb = removeSpace(s);
        reverseString(sb, 0, sb.length()-1);
        reverseEachWord(sb);
        return sb.toString();
    }

    //删除首尾以及单词之间多余的空格
    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++;
        }
        return sb;
    }

    private void reverseString(StringBuilder sb, int start, int end){
        while(start < end){
            char temp = sb.charAt(start);
            sb.setCharAt(start, sb.charAt(end));
            sb.setCharAt(end, temp);
            start++;
            end--;
        }
    }

    private void reverseEachWord(StringBuilder sb){
        int i = 0;
        int j = 1;

        while(i<sb.length()){
            while(j<sb.length() && sb.charAt(j) != ' ') j++;  //先让j到该单词的末尾

            reverseString(sb, i, j-1);
            i = j+1;
            j = i+1;
        }
    }
}

| String是不可变长，如果要改变此字符串的长度，建议换成变长字符串好操作，最后再按要求变回来

快指针就是读指针，所以要全部读一遍，慢指针就是写指针，需要的时候再写

二、卡码网55.右旋转字符串

题目：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

思路：先全部翻转；然后截取k位置，把字符串分成两部分；再把两部分分别进行局部翻转

注意：ACM模式下，其他方法要static

import java.util.*;

public class Main{
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = Integer.parseInt(sc.nextLine());
        String s = sc.nextLine();
        
        StringBuilder sb = new StringBuilder(s);
        
        //整体反转
        reverseString(sb, 0, sb.length()-1);
        
        //k之前反转
        reverseString(sb,0,k-1);
        //k之后反转（剩余部分）
        reverseString(sb,k,sb.length()-1);
        
        System.out.println(sb);
    }
    
    private static void reverseString(StringBuilder s, int start, int end){
        while(start < end){
            char temp = s.charAt(start);
            s.setCharAt(start, s.charAt(end));
            s.setCharAt(end, temp);
            
            start++;
            end--;
        }
    }
}

尝试过程：

import java.util.*;

public class Main{
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        // int k = sc.next;
        int k = Integer.parseInt(sc.nextLine());  //
        String s = sc.nextLine();
        
        StringBuilder sb = new StringBuilder(s);
        
        reverseString(sb, 0, sb.length()-1);
       
        reverseString(sb,0,k-1);
        reverseString(sb,k,sb.length()-1);
        
        System.out.println(sb);    
    }
    
    private void reverseString(StringBuilder s, int start, int end){   //static
        while(start < end){
            char temp = s.charAt(start);    
            s.setCharAt(start, s.charAt(end));
            s.setCharAt(end, temp);
            
            start++;
            end--;
        }
    }

}