代码随想录算法训练营第八天|Leetcode 151.翻转字符串里的单词 卡码网：55.右旋转字符串 字符串总结 双指针回顾

151.翻转字符串里的单词

建议：这道题目基本把 刚刚做过的字符串操作 都覆盖了，不过就算知道解题思路，本题代码并不容易写，要多练一练。

题目链接/文章讲解/视频讲解：代码随想录

我们这道题的思路是，先将整个字符串反转，结束之后再定位每一个单词，然后再将单词进行反转，思路为什么是这样子的呢

为什么要先翻转整个字符集，再翻转单词，而不是直接翻转单词

假设输入字符串: "hello world"

方法1 (当前代码采用的方法):
1. 整体翻转: "dlrow olleh"
2. 单词翻转: "world hello"

方法2 (直接翻转单词):
这需要:
1. 找到每个单词的位置
2. 将单词存储到新的位置
3. 处理单词之间的空格
4. 可能需要额外的存储空间来临时保存单词

当前方法的优势:
1. 空间复杂度低：只需要在原字符串上操作，不需要额外空间存储单词
2. 实现简单：只需要简单的字符交换操作
3. 时间复杂度稳定：只需要遍历字符串固定的次数

直接翻转单词的劣势:
1. 需要额外的空间来存储单词
2. 需要处理单词移动的复杂逻辑
3. 实现起来更复杂，容易出错
 

如果我们直接对单词进行反转，我举个例子

“hello world”

反转之后应该是“world hello”

如果不将字符串先进行反转，我们直接反转的话，需要额外的空间，因为数组的操作从根本上来说是覆盖操作，那么我们在写world的时候就会将hello覆盖，所以我们需要格外的空间存储hello才行，这样就把逻辑变复杂了，如果先翻转再单词内部反转，适度简化了逻辑。

我们来看代码

public String reverseWords(String s) {
    // 第一步：调用removeSpace去除多余空格
    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;
    
    // 移动start指针，跳过开头的空格
    while (s.charAt(start) == ' ') start++;
    // 移动end指针，跳过结尾的空格
    while (s.charAt(end) == ' ') end--;
    
    // 创建StringBuilder存储结果
    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 (start < end) {
        // 交换start和end位置的字符
        char temp = sb.charAt(start);
        sb.setCharAt(start, sb.charAt(end));
        sb.setCharAt(end, temp);
        // 移动指针
        start++;
        end--;
    }
}
private void reverseEachWord(StringBuilder sb) {
    // start指向单词的开始，end指向下一个字符
    int start = 0;
    int end = 1;
    int n = sb.length();
    
    while (start < n) {
        // 移动end直到找到单词的结束位置（空格或字符串末尾）
        while (end < n && sb.charAt(end) != ' ') {
            end++;
        }
        // 反转当前单词
        reverseString(sb, start, end - 1);
        // 更新start和end，准备处理下一个单词
        start = end + 1;
        end = start + 1;
    }
}

卡码网：55.右旋转字符串

建议：题解中的解法如果没接触过的话，应该会想不到

题目链接/文章讲解：

右旋转