字符串翻转算法：双指针与反转技巧实战

1. 字符串翻转算法实战解析

作为一名经历过多次算法面试的老手，我深知字符串处理是面试中的高频考点。今天我想分享两个经典的字符串翻转问题，它们都巧妙地运用了"整体反转+局部反转"的思想。这种解法不仅高效，而且能帮助我们深入理解指针操作和字符串处理的精髓。

2. LeetCode 151：翻转字符串中的单词

2.1 问题分析与解题思路

这道题要求我们将字符串中的单词顺序翻转，同时去除多余空格。例如：
输入："the sky is blue"
输出："blue is sky the"

常规解法可能会想到用栈或者split方法，但这样空间复杂度会达到O(n)。更优的解法是采用三步走策略：

1. 移除多余空格（双指针法）
2. 反转整个字符串
3. 逐个反转每个单词

这种方法的优势在于：

• 时间复杂度O(n)
• 空间复杂度O(1)（原地修改）
• 避免使用额外数据结构

2.2 代码实现与细节解析

cpp复制class Solution {
public:
    void reverse(string& s, int start, int end) {
        for (int i = start, j = end; i < j; i++, j--) {
            swap(s[i], s[j]);
        }
    }

    void removeExtraSpaces(string& s) {
        int slow = 0;   
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] != ' ') {
                if (slow != 0) s[slow++] = ' ';
                while (i < s.size() && s[i] != ' ') {
                    s[slow++] = s[i++];
                }
            }
        }
        s.resize(slow);
    }

    string reverseWords(string s)