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

发布于:2025-02-10 ⋅ 阅读:(46) ⋅ 点赞:(0)

一、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--;
        }
    }

}

| 左旋和右旋是字符串操作中的两个概念,它们描述了字符串中字符的移动方向:

左旋(Left Rotate)是将字符串中的前若干个字符移动到字符串的末尾。例如,对于字符串 “abcdefg” 和整数 2,进行左旋操作后,字符串变为 “cdefgab”。这意味着原本在前面的字符(在这个例子中是 “ab”)被移到了字符串的后面。

右旋(Right Rotate)是将字符串中的后若干个字符移动到字符串的前面。例如,对于字符串 “abcdefg” 和整数 2,进行右旋操作后,字符串变为 “fgabcde”。这意味着原本在后面的字符(在这个例子中是 “fg”)被移到了字符串的前面。

注意,在某些情况下,左旋和右旋的结果可能看起来相同,但这并不意味着它们是相同的操作。它们的区别在于字符移动的方向和操作的逻辑。


三、KMP(跳过)

题目:

视频:

讲解:



四、总结

反转系列

当需要固定规律一段一段去处理字符串的时候,要想想在for循环的表达式上做做文章。

先整体反转再局部反转

双指针法

双指针法在数组,链表和字符串中很常用。

— 数组篇:

使用双指针法才展现出效率的优势:通过两个指针在一个for循环下完成两个for循环的工作。

— 字符串篇:

使用双指针法,定义两个指针(也可以说是索引下标),一个从字符串前面,一个从字符串后面,两个指针同时向中间移动,并交换元素。

其实很多数组填充类的问题,都可以先预先给数组扩容到填充后的大小,然后再从后向前进行操作。

— 链表篇:

翻转链表是现场面试,白纸写代码的好题,考察了候选者对链表以及指针的熟悉程度,而且代码也不长,适合在白纸上写。

只需要改变链表的next指针的指向,直接将链表反转 ,而不用重新定义一个新的链表。

使用快慢指针(双指针法),分别定义 fast 和 slow指针,从头结点出发,fast指针每次移动两个节点,slow指针每次移动一个节点,如果 fast 和 slow指针在途中相遇 ,说明这个链表有环。

— N数之和篇:

两数之和:哈希法

三数之和:哈希法并不适用,使用双指针法才是最为合适的,通过前后两个指针不断向中间逼近,在一个for循环下完成两个for循环的工作。

四数之和:在三数之和的基础上再套一层for循环,依然是使用双指针法。

同样的道理,五数之和,n数之和都是在这个基础上累加。

— 总结

使用双指针来提高效率,一般是将O(n^2)的时间复杂度,降为 O ( n ) O(n) O(n)


网站公告

今日签到

点亮在社区的每一天
去签到