力扣面试经典——151题

💡 参考代码：

/**
 * 移除字符串中的多余空格
 * @param s 输入字符串
 * @return 处理后的字符串长度
 */
int removeExtraSpaces(char* s) {
    int slow = 0;
    int fast = 0;
    
    // 跳过前导空格
    while (s[fast] == ' ') {
        fast++;
    }
    
    // 处理中间部分：移除单词间多余的空格
    while (fast < strlen(s)) {
        // 如果当前字符不是空格，或者是第一个空格，则保留
        if (s[fast] != ' ' || (fast > 0 && s[fast - 1] != ' ')) {
            s[slow++] = s[fast];
        }
        fast++;
    }
    
    // 处理结尾可能的空格
    if (slow > 0 && s[slow - 1] == ' ') {
        slow--;
    }
    
    s[slow] = '\0';  // 添加字符串结束符
    return slow;
}

/**
 * 反转字符串指定范围内的字符
 * @param s 字符串
 * @param start 起始位置（包含）
 * @param end 结束位置（包含）
 */
void reverseString(char* s, int start, int end) {
    while (start < end) {
        char temp = s[start];
        s[start] = s[end];
        s[end] = temp;
        start++;
        end--;
    }
}

/**
 * 反转字符串中单词的顺序
 * @param s 输入字符串
 * @return 反转后的字符串
 */
char* reverseWords(char* s) {
    // 第一步：移除多余空格
    int len = removeExtraSpaces(s);
    
    // 第二步：反转整个字符串
    reverseString(s, 0, len - 1);
    
    // 第三步：反转每个单词
    int start = 0;
    for (int i = 0; i <= len; i++) {
        // 遇到空格或字符串结尾时，反转当前单词
        if (s[i] == ' ' || s[i] == '\0') {
            reverseString(s, start, i - 1);
            start = i + 1;
        }
    }
    
    return s;
}

📖 总结：

点击展开题目总结

🤔 反转字符串中的单词

---

1️⃣ 题目核心信息

🎯 功能描述：给定一个字符串，反转其中单词的顺序，同时处理多余的空格问题

📥 输入输出：

• 输入：char* s - 输入的字符串，可能包含前导空格、尾随空格或单词间多个空格
• 输出：char* - 返回单词顺序颠倒且单词间仅用单个空格分隔的字符串

---

2️⃣ 实现原理

💡 核心思路：使用双指针技术移除多余空格，然后通过整体反转加局部反转的方式实现单词顺序调换

📋 实现步骤：

1. 使用双指针移除字符串中的前导空格、尾随空格和单词间的多余空格
2. 反转整个字符串
3. 遍历字符串，识别每个单词的边界并单独反转每个单词
4. 返回处理后的字符串

---

3️⃣ 关键点解析

🎯 代码技巧

• 双指针技术：用于高效地移除多余空格，避免使用额外空间
• 两次反转法：先整体反转再局部反转，巧妙实现单词顺序调换
• 原地操作：所有操作都在原字符串上进行，满足O(1)空间复杂度要求

4️⃣ 使用场景

✅ 适用情况：

• 需要反转句子中单词顺序的文本处理
• 内存受限环境下处理字符串
• 需要规范化空格的字符串处理场景

⚠️ 前提条件：

• 字符串必须是可变的（C语言中为字符数组）
• 字符串至少包含一个单词

5️⃣ 复杂度分析

• ⏱️ 时间复杂度：O(n)，其中n是字符串长度，需要遍历字符串常数次

• 💾 空间复杂度：O(1)，只使用常数级别的额外空间，原地修改字符串

6️⃣ 注意事项

🚩 边界情况：

• 空字符串或只包含空格的字符串
• 只有一个单词的字符串
• 字符串中包含大量多余空格的情况

💥 易错点：

• 忘记处理前导空格和尾随空格
• 单词间空格处理不正确，可能保留多个空格
• 反转区间边界处理错误，导致数组越界

7️⃣ 补充说明

以字符串 " the sky is blue " 为例来演示整个算法过程：

初始状态

输入字符串：" the sky is blue "

第一步：移除多余空格

执行 removeExtraSpaces 函数：

原字符串: "  the sky is blue  "
          ↑
        fast=0, slow=0

过程：

• fast=0,1: 空格，跳过
• fast=2: 't' -> s[0]='t', slow=1
• fast=3: 'h' -> s[1]='h', slow=2
• fast=4: 'e' -> s[2]='e', slow=3
• fast=5: 空格 -> s[3]=' ', slow=4
• fast=6: 空格 -> 与前一字符都是空格，跳过
• fast=7: 's' -> s[4]='s', slow=5
• fast=8: 'k' -> s[5]='k', slow=6
• fast=9: 'y' -> s[6]='y', slow=7
• fast=10: 空格 -> s[7]=' ', slow=8
• fast=11: 'i' -> s[8]='i', slow=9
• fast=12: 's' -> s[9]='s', slow=10
• fast=13: 空格 -> s[10]=' ', slow=11
• fast=14: 'b' -> s[11]='b', slow=12
• fast=15: 'l' -> s[12]='l', slow=13
• fast=16: 'u' -> s[13]='u', slow=14
• fast=17: 'e' -> s[14]='e', slow=15
• fast=18,19: 空格 -> 检查到结尾空格，不做处理

最终结果: "the sky is blue" 索引: 0123456789ABCDEF 长度: 15

第二步：反转整个字符串

执行 reverseString(s, 0, 14)：

原字符串: "the sky is blue"
反转后:   "eulb si yks eht"

第三步：逐个反转单词

遍历字符串，对每个单词进行反转：

1.处理第一个单词 "eulb"（索引0-3）：

反转前: "eulb si yks eht"
反转后: "blue si yks eht"

2.处理第二个单词 "si"（索引5-6）：

反转前: "blue si yks eht"
反转后: "blue is yks eht"

3.处理第三个单词 "yks"（索引8-10）：

反转前: "blue is yks eht"
反转后: "blue is sky eht"

4.处理第四个单词 "eht"（索引12-14）：

反转前: "blue is sky eht"
反转后: "blue is sky the"  

最终结果

输出字符串："blue is sky the"

这个过程通过三步操作完成了单词顺序的反转：

1.首先清理输入字符串，移除多余空格

2.然后整体反转字符串

3.最后将每个单词再次反转以恢复其正确顺序

这种方法的优势在于只需要常数级别的额外空间，完全在原字符串上进行操作。

加载评论中...