算法珠玑——双指针(3)

用例太少了！我觉得这个代码比官方快多了，但是估计也被运气影响了。

class Solution {
public:
    string reverseWords(string s) {
        /*
            基本情况：left(1) = 0;
                    right(1) = k_1 - 1;
            声明在外，提高性能
        */
        int right;
        int len = s.size()+1;

        /*
            终止情况: k < s.size() 不成立
            归纳步骤: 若 s[k] == ' ' || !s[k]
                    left = k(n-1) + 1, right = k(n) - 1
                    然后使用这两个变量进行反转的第二个归纳应用
        */
        // 为了内存，left定义到这里了
        for (int k = 0, left = 0; k < len; k++)
        {
            // 这是个短路判断，只有最后一个单词会进入!s[k]情况
            if (s[k] == ' ' || !s[k])
            {
                /*
                    基本情况: left = k(n-1) + 1, right = k(n)-1
                    终止情况: left < right 不成立
                    归纳步骤: 交换s[left] 和 s[right]
                */
                for (right = k - 1; left < right; left++, right--)
                    swap(s[left], s[right]);
                left = k + 1;
            }
        }
        
        return s;
    }
};

这题在速度上可以将!s[k]部分单独提出来，不过这样的话内存就会加一点。