试水刷题，先从简单的练起。

题目

151. 翻转字符串里的单词

给定一个字符串，逐个翻转字符串中的每个单词。

示例 1：

输入: "the sky is blue"
输出: "blue is sky the"

示例 2：

输入: " hello world! "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

示例 3：

输入: "a good example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

说明：

• 无空格字符构成一个单词。
• 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
• 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

进阶：

请选用 C 语言的用户尝试使用 O(1) 额外空间复杂度的原地解法。

解题思路

利用各个语言的内置方法，其实可以简简单单 split 再反转再拼接，但是那也太没意思了。

直接抄起 C 语言，来试试 O(1) 额外空间复杂度的原地解法。

先来构造一个样例：" hello haha world! "

这个样例同时包含了多种多余空格：前导空格、连续空格、尾部空格。

为了便于查看，图示中使用 # 来代指空格。

样例看起来就像 "###hello#haha##world!#"，在内存中大概是下图这样。

那么我们首先通过对 s 指针进行移动，把前面多余空格跳过。

接下来使用 left, right 两个变量，构造窗口寻找单词。

right 找到空格之后，意味着黄色区域为一整个单词。

对黄色区域进行翻转，翻转完成后将 left 指向 right+1，也就是下一个单词的开头位置。

以上是正常情况，接下来处理连续空格的情况，当处理完 haha 这个单词的翻转之后， left right 同时遇到了空格，此时记录一下 offset 偏移量。

多余的空格我们先不处理，继续找单词，找到合适的单词准备翻转。

翻转的时候需要注意，因为 offset 的存在，实际上这个翻转过程是斜着的，类似于先将单词平移，再进行翻转。（代码中并不需要两个步骤，合理利用 offset 变量即可）

终于，我们跑到了字符串的尾部，也就是 \0 ，需要注意的是，如果尾部紧跟着空格， offset 标记也要自增。

接下来的工作就很轻松了，我们首先处理长度，offset 标记告诉我们，这个字符串里有两个多余的空格，所以我们直接算出合适的位置，将字符串截断一下。

然后，将整个字符串翻转一下就搞掂啦~

解答

C 代码

char *reverseWords(char *s) {
    // 处理特殊情况
    while (s[0] == ' ')
        s += 1;
    if (s[0] == '\0')
        return s;

    int offset = 0, left = 0, right = 0;
    while (++right) {
        if (s[right] == ' ' || s[right] == '\0') {
            if (right == left) {    
                // 遇到连续空格
                offset += 1;    
            } else {
                // 遇到单词，将单词倒序，注意 offset          
                for (int i = 0; i < (right - left + offset + 1) / 2; i++) {
                    char tmp = s[left + i - offset];
                    s[left + i - offset] = s[right - 1 - i];
                    if (i >= offset)
                        s[right - 1 - i] = tmp;
                }
                // 注意补空格
                if (offset != 0)    
                    s[right - offset] = ' ';
            }
            // 将 left 指到下一个单词的开头
            left = right + 1;       
        }
        if (s[right] == '\0')
            break;
    }

    // 截断字符串
    right -= offset;
    s[right] = '\0';    
    // 将字符串倒序
    for (int j = 0; j < right / 2; j++) {
        char tmp = s[j];
        s[j] = s[right - 1 - j];
        s[right - 1 - j] = tmp;
    }
    return s;
}

实际上，对字符串倒序的时候也可以不声明 j 变量，直接使用 right 递减即可（也可以用 right left 双向），不过影响不大就不折腾了。

原地解法效率不错，轻松双百：