代码随想录day9 | leetcode151.翻转字符串里的单词卡码网：55.右旋转字符串暂时跳过KMP内容字符串总结双指针回顾

🕗 发布于 2024-12-12 01:32 java leetcode 算法 数据结构

151.翻转字符串里的单词

写三个函数方法来实现

class Solution {
    public String reverseWords(String s) {
        StringBuilder sb = removeExtraSpaces(s);
        
        reverseString(sb, 0, sb.length()-1);
        reverseEachWord(sb);
        return sb.toString();
    }
    private StringBuilder removeExtraSpaces(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; 
    }
    public void reverseString(StringBuilder sb, int start, int end) {
        while(end >= start) {
            char temp = sb.charAt(start);
            sb.setCharAt(start, sb.charAt(end));
            sb.setCharAt(end, temp);
            end--;
            start++;
        }
    }
    private void reverseEachWord(StringBuilder sb) {
        int start = 0;
        int end = 1;
        int n = sb.length();
        while(start < n) {
            while(end < n && sb.charAt(end) != ' ') {
                end++;
            }
            reverseString(sb, start, end - 1);
            start = end + 1;
            end = start +1;
        }
    }
}

`removeExtraSpaces`

1. 去除前导和尾部空格

while (s.charAt(start) == ' ') start++;
while (s.charAt(end) == ' ') end--;

start 指针：从字符串的开头开始，跳过所有的空格，直到找到第一个非空格字符。
end 指针：从字符串的结尾开始，跳过所有的空格，直到找到第一个非空格字符。

这两步确保了字符串的前导和尾部空格被去除。

2. 创建 `StringBuilder`

StringBuilder sb = new StringBuilder();

StringBuilder 用于构建最终的字符串，避免了在字符串拼接过程中频繁创建新的字符串对象，提供了更好的性能。

3. 遍历字符串，处理多余空格

while (start <= end) {
    char c = s.charAt(start);
    
    // 如果当前字符不是空格，或者是空格但 sb 的末尾不是空格
    if (c != ' ' || sb.charAt(sb.length() - 1) != ' ') {
        sb.append(c);
    }
    start++;
}

这一段的核心逻辑是通过 start 指针遍历字符串中的字符。
每次读取一个字符 c，并判断它是否是空格。- 如果字符 c 不是空格，那么直接将字符添加到 StringBuilder 中。
- 如果字符 c 是空格，只有在 StringBuilder 的末尾不是空格时，才会将空格添加到 StringBuilder 中。这就保证了不会在两个单词之间添加多余的空格。

为什么能在两个单词之间留下一个空格？

假设字符串中有两个单词，"Hello World"，去除前后的空格后，剩下的是 "Hello World"。- 在遍历过程中，遇到 "Hello" 后，会将 "Hello" 添加到 StringBuilder 中。
- 然后会遇到一系列的空格（' ' ' ' ' '）。这些空格会被跳过，直到遇到下一个非空格字符 'W'（即 "World"）。
- 此时，StringBuilder 末尾没有空格，所以下一个字符 ' ' 会被添加，这样就会在 "Hello" 和 "World" 之间添加一个空格。
通过检查 sb.charAt(sb.length() - 1) != ' ' 来保证只有一个空格会被添加到 StringBuilder 中，从而避免多个空格出现在单词之间。

`reverseString`

setCharAt(int index, char ch) 是 StringBuilder 和 StringBuffer 类中的一个方法，用于修改字符串中特定位置的字符。它允许你直接修改字符序列中的某个位置的字符，而不需要重新创建一个新的字符串或字符数组。

功能：

setCharAt 方法将字符 ch 替换到 StringBuilder 或 StringBuffer 中指定位置 index 上的字符。
这意味着你可以直接对某个索引位置的字符进行修改，而不需要重新创建整个字符串。

`reverseEachWord`

初始化变量：
- start = 0：表示当前单词的开始位置，初始值为字符串的开始位置。
- end = 1：表示当前单词的结束位置，初始值为 start + 1，即从 start 后面的第一个字符开始检查。
- n = sb.length()：获取 StringBuilder 的长度，用于确定结束条件。
查找单词：
```
while (end < n && sb.charAt(end) != ' ') {
    end++;
}
```
- 这部分代码的作用是查找下一个空格字符或字符串末尾，end 用来标记当前单词的结束位置。如果 end 指向的不是空格且还没有到达字符串末尾，end 会继续向后推进，直到遇到空格或字符串末尾。
反转单词：
```
reverseString(sb, start, end - 1);
```
- 这行调用了 reverseString(sb, start, end - 1) 方法来反转从 start 到 end - 1 的字符序列。end - 1 是当前单词的最后一个字符位置，因为 end 是指向下一个空格位置的。
更新 start 和 end 指针：
```
start = end + 1;
end = start + 1;
```
- 在反转当前单词后，start 更新为 end + 1，即跳过当前单词后面的空格，开始下一个单词的操作。
- 同时，end 更新为 start + 1，为下一个单词的结束位置做准备。
重复直到处理完所有单词：
- 整个 while (start < n) 循环会一直执行，直到处理完所有的单词。

示例：

假设 sb 为 "Hello world"，执行这段代码的过程如下：

初始：sb = "Hello world"
- start = 0, end = 1
第一次 while 循环：找到 "Hello"（end 最终指向空格的位置），然后调用 reverseString(sb, 0, 4)，反转 "Hello" 为 "olleH"。
- sb = "olleH world"
- 更新：start = 6, end = 7
第二次 while 循环：找到 "world"（end 最终指向字符串末尾），然后调用 reverseString(sb, 6, 10)，反转 "world" 为 "dlrow"。
- sb = "olleH dlrow"
最终结果：sb = "olleH dlrow"

卡码网 55.右旋字符串

Java不能在字符串上修改，所以使用java一定要开辟新空间

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = Integer.parseInt(sc.nextLine());
        String s = sc.nextLine();
        
        int len = s.length();
        char[] ch = s.toCharArray();
        
        // 对字符串的前一部分进行反转
        reverseString(ch, 0, len - n - 1);
        
        // 对字符串的后一部分进行反转
        reverseString(ch, len - n, len - 1); //是len-n而不是len-n-1 len-n-1指向结尾
        
        // 反转整个字符串
        reverseString(ch, 0, len - 1);
        
        System.out.println(ch);
    }

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

总结：

通过三个步骤（a ^= b，b ^= a，a ^= b），a和b的值得以交换，且不需要额外的临时变量。这就是所谓的异或交换。使用异或交换的关键是利用了异或运算的性质：

x ^ x = 0（任何数与自身异或得到0），
x ^ 0 = x（任何数与0异或得到它本身），
x ^ y = y ^ x（异或运算具有交换性）。

因此，最终交换完成后，a和b的值互换。

异或交换的步骤解析：

对于ch[start]和ch[end]进行异或交换：

ch[start] ^= ch[end]; // 第一次操作：ch[start]变成ch[start] ^ ch[end]
ch[end] ^= ch[start];  // 第二次操作：ch[end]变成原来的ch[start]
ch[start] ^= ch[end];  // 第三次操作：ch[start]变成原来的ch[end]

第一次异或后，ch[start]保存了ch[start]和ch[end]的异或结果。
第二次异或后，ch[end]被赋值为ch[start]的原值。
第三次异或后，ch[start]被赋值为ch[end]的原值。

KMP算法理解了理论代码实现没理解放一放

字符串总结

字符串类类型的题目，往往想法比较简单，但是实现起来并不容易，复杂的字符串题目非常考验对代码的掌控能力。
双指针法是字符串处理的常客。
KMP算法是字符串查找最重要的算法，现在我没有理解代码如何实现先放一放

1.双指针法

在344.反转字符串，使用双指针法实现了反转字符串的操作，双指针法在数组，链表和字符串中很常用。
接着在卡玛网 54.替换空格，同样还是使用双指针法在时间复杂度O(n)的情况下完成替换空格。
其实很多数组填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作。
那么针对数组删除操作的问题，其实在27. 移除元素中就已经提到了使用双指针法进行移除操作。
同样的道理在151.翻转字符串里的单词中我们使用O(n)的时间复杂度，完成了删除冗余空格。
用库函数erase来移除元素，这其实是O(n^2)的操作，因为erase就是O(n)的操作，所以这也是典型的不知道库函数的时间复杂度，上来就用的案例了。

2.反转系列

在反转上还可以在加一些玩法，其实考察的是对代码的掌控能力。
541. 反转字符串中，一些同学可能为了处理逻辑：每隔2k个字符的前k的字符，写了一堆逻辑代码或者再搞一个计数器，来统计2k，再统计前k个字符。
其实当需要固定规律一段一段去处理字符串的时候，要想想在在for循环的表达式上做做文章。
只要让 i += (2 * k)，i 每次移动 2 * k 就可以了，然后判断是否需要有反转的区间。
因为要找的也就是每2 * k 区间的起点，这样写程序会高效很多。
在[151.翻转字符串里的单词]中要求翻转字符串里的单词，这道题目可以说是综合考察了字符串的多种操作。是考察字符串的好题。
这道题目通过 先整体反转再局部反转，实现了反转字符串里的单词。
后来发现反转字符串还有一个牛逼的用处，就是达到左旋的效果。
在卡码网 55.左旋字符串中，我们通过先局部反转再整体反转达到了左旋的效果。

3.KMP

KMP的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。
KMP的精髓所在就是前缀表。
前缀表：起始位置到下标i之前（包括i）的子串中，有多大长度的相同前缀后缀。
那么使用KMP可以解决两类经典问题：

匹配问题：28. 实现 strStr()
重复子串问题：459.重复的子字符串
前缀：指不包含最后一个字符的所有以第一个字符开头的连续子串。

双指针总结篇

数组篇

原地移除数组上的元素，我们说到了数组上的元素，不能真正的删除，只能覆盖。
一些同学可能会写出如下代码（伪代码）：

for (int i = 0; i < array.size(); i++) {
    if (array[i] == target) {
        array.erase(i);
    }
}

这个代码看上去好像是O(n)的时间复杂度，其实是O(n^2)的时间复杂度，因为erase操作也是O(n)的操作。
所以此时使用双指针法才展现出效率的优势：通过两个指针在一个for循环下完成两个for循环的工作。

字符串篇

在day8 334.反转字符串中讲解了反转字符串，注意这里强调要原地反转，要不然就失去了题目的意义。
使用双指针法，定义两个指针（也可以说是索引下标），一个从字符串前面，一个从字符串后面，两个指针同时向中间移动，并交换元素。，时间复杂度是O(n)。
在day8 卡玛网 54.替换空格 中介绍使用双指针填充字符串的方法，如果想把这道题目做到极致，就不要只用额外的辅助空间了！
思路就是首先扩充数组到每个空格替换成"%20"之后的大小。然后双指针从后向前替换空格。
有同学问了，为什么要从后向前填充，从前向后填充不行么？
从前向后填充就是O(n^2)的算法了，因为每次添加元素都要将添加元素之后的所有元素向后移动。
其实很多数组（字符串）填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作。
那么在day 9 151.翻转字符串里的单词中，我们使用双指针法，用O(n)的时间复杂度完成字符串删除类的操作，因为题目要删除冗余空格。
在删除冗余空格的过程中，如果不注意代码效率，很容易写成了O(n^2)的时间复杂度。其实使用双指针法O(n)就可以搞定。
主要还是大家用erase用的比较随意，一定要注意for循环下用erase的情况，一般可以用双指针写效率更高！

链表篇

翻转链表是现场面试，白纸写代码的好题，考察了候选者对链表以及指针的熟悉程度，而且代码也不长，适合在白纸上写。
在day3 206.反转链表中，讲如何使用双指针法来翻转链表，只需要改变链表的next指针的指向，直接将链表反转，而不用重新定义一个新的链表。
思路还是很简单的，代码也不长，但是想在白纸上一次性写出bugfree的代码，并不是容易的事情。
在链表中求环，应该是双指针在链表里最经典的应用，在day4 142.环形链表中讲解了如何通过双指针判断是否有环，而且还要找到环的入口。
使用快慢指针（双指针法），分别定义 fast 和 slow指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针在途中相遇，说明这个链表有环。
如何找到环的入口，day4 142.环形链表 也有解释。

N数之和篇

在day7 5.三数之和中，讲到使用哈希法可以解决day6 1.两数之和的问题
其实使用双指针也可以解决day6 1.两数之和的问题，只不过day6 1.两数之和求的是两个元素的下标，没法用双指针，如果改成求具体两个元素的数值就可以了。
使用了哈希法解决了两数之和，但是哈希法并不适用于三数之和！
使用哈希法的过程中要把符合条件的三元组放进数组中，然后在去去重，这样是非常费时的，很容易超时，也是三数之和通过率如此之低的根源所在。
去重的过程不好处理，有很多小细节，如果在面试中很难想到位。
时间复杂度可以做到O(n^2)，但还是比较费时的，因为不好做剪枝操作。
所以这道题目使用双指针法才是最为合适的，用双指针做这道题目才能就能真正体会到，通过前后两个指针不断向中间逼近，在一个for循环下完成两个for循环的工作。
只用双指针法时间复杂度为O(n^2 ），但比哈希法的O(n^2)效率高得多，哈希法在使用两层for循环的时候，能做的剪枝操作很有限。
在day7 18.四数之和中，讲到了四数之和，其实思路是一样的，在三数之和的基础上再套一层for循环，依然是使用双指针法。
对于三数之和使用双指针法就是将原本暴力O(n^{3)的解法，降为O(n}2)的解法，四数之和的双指针解法就是将原本暴力O(n^{4)的解法，降为O(n}3)的解法。
同样的道理，五数之和，n数之和都是在这个基础上累加。

总结

本文中一共介绍了leetcode上九道使用双指针解决问题的经典题目，除了链表一些题目一定要使用双指针，其他题目都是使用双指针来提高效率，一般是将O(n^2)的时间复杂度，降为 O(n) 。

原文地址：https://blog.csdn.net/2302_81139517/article/details/144273906

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：【Nestjs实操】TypeORM装饰器汇总
下一篇：算法-字符串-227.基本计算器||

.NET(C#) 如何配置用户首选项及保存用户设置
.NET(C#) 如何配置用户首选项及保存用户设置
阅读更多2024-12-14
【最新】北大数字普惠金融指数数据集-省市县（2011-2023年）
郭峰,王靖一,王芳,孔涛,张勋,程志云.测度中国数字普惠金融发展:指数编制与空间特征[J].经济学(季刊),2020,19(04):1401-1418.时间跨度：省级和城市级指数时间跨度为2011-2
阅读更多2024-12-14
GESP202412 四级【Recamán】题解（AC）
a11ak−1−kkakak−1−kak−1k小杨想知道 Recamán 数列的前n项从小到大排序后的结果。手动计算非常困难，小杨希望你能帮他解决这个问题。
阅读更多2024-12-14
IDEA遇到EasyConnect中的网络资源无法访问的问题
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。原文链接：https://blog.csdn.net/wanshanyu_/article/de
阅读更多2024-12-14
双目摄像头标定方法
此时已经完成标定，左下角为反投影误差，右边为外参可视化。将双目左右目拍的图像上传（左右目最好不少于20张）此时回到主页面，即可看到成功导出。把这些误差大的删除即可。
阅读更多2024-12-14
Servlet、omcat服务器架构与工作原理
Servlet是运行在服务器端的Java程序，它的主要职责之一是接收并处理来自客户端（如浏览器）的HTTP请求。当客户端发送一个请求到服务器时，Servlet可以解析请求中的信息，例如请求的URL路径
阅读更多2024-12-14
Vue生命周期钩子函数：深入解析与实践
作为高级Vue前端开发人员，对Vue组件的生命周期钩子函数有着深刻的理解是至关重要的。生命周期钩子函数是指在Vue组件的创建、更新、销毁等过程中，Vue自动调用的一系列方法。通过这些钩子函数，我们可以
阅读更多2024-12-14
安卓开发--使用android studio发布APP
app发布
阅读更多2024-12-14
数据结构与算法学习笔记----拓扑排序
@ author: 明月清了个风。
阅读更多2024-12-14
python 将数据保存到现有的Excel文件的新工作表
out_file = ‘query.xlsx’df1 = pd.DataFrame(out_data)若直接写入：df1.to_excel(out_file, index=False, sheet_n
阅读更多2024-12-14

代码随想录day9 | leetcode151.翻转字符串里的单词 卡码网：55.右旋转字符串 暂时跳过KMP内容 字符串总结 双指针回顾