2019-04-05

151. 翻转字符串里的单词

• 去空格 多个只保留一个，字符串开始不是空格
• 单词顺序不变，但是字符串位置发生了翻转

测试

输入: " hello world! "
输出: "world! hello"

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

开头存在空格 只存在一个空格 结尾存在空格

方法1 不需要考虑任何复杂情况

执行用时 : 16 ms, 在Reverse Words in a String的C++提交中击败了16.12% 的用户
内存消耗 : 10.6 MB, 在Reverse Words in a String的C++提交中击败了0.93% 的用户
class Solution {
public:
    string reverseWords(string s) {
        stack<string> stk;//LIFO context (last-in first-out)
        int pos = 0;
        string res;

        while (pos < s.length()) {
            int end, start;
            
            while(s[pos] == ' ' && pos < s.length())
                pos++;
            
            start = pos;
            
            while (s[pos] != ' ' && pos < s.length())
                pos++;
            
            end = pos;

            if (end == start)
                break;
            
            stk.push(s.substr(start, end - start));
        }

        while (!stk.empty()) {
            res += stk.top();
            stk.pop();
            if (!stk.empty())
                res += " ";
        }

        return res;
    }
};

旁白：

• while适合用于状态变化控制，说高大上点就是while适合做状态机，而for仅仅是为了循环而循环
• while语句的历史更久，表达方式上更自由灵活，常用于无法事先判断循环次数的循环。譬如经典的计算C风格字符串的长度的代码，又如后根遍历二叉树的非递归实现。此时用while语句会使程序更清晰。
• 嵌套循环应该遵循“外小内大”的原则

方法2 去空格 然后翻转

class Solution {
public:
    void reverse(string &s, int l, int r) {
        while (l < r) swap(s[l++], s[r--]);
    }
    void reverseWords(string &s) {
        int w = 0, r = 0, sz = s.size();
        while (r < sz) {
            if (s[r] == ' ') {
                ++r;
                if (w - 1 >= 0 && s[w - 1] != ' ' && r < sz) s[w++] = ' '; // if not added space
            }
            else s[w++] = s[r++];
        }

        s.resize(w);
        if (s.back() == ' ') s.resize(s.size() - 1); // remove possible space at the end of string
        w = r = 0, sz = s.size();
        while (r < sz) {
            while (r < sz && s[r] != ' ') ++r;
            reverse(s, w, r - 1);
            while (r < sz && s[r] == ' ') ++r;
            w = r;
        }
        reverse(s, 0, sz-1);
    }
};

方法3 合并1和2

class Solution {
public:
    void reverseWords(string &s) {
        int sz = s.size();
        int i = 0, j = 0;
        while (i < sz)
        {
            while (i < sz && s[i] == ' ') i++; //i is the start of the word
            if (i < sz && j > 0)
                s[j++] = ' ';
            int start = j;
            while (i < sz && s[i] != ' ')
                s[j++] = s[i++];
            reverse(s.begin()+start, s.begin()+j);
        }
        s.resize(j);
        reverse(s.begin(), s.end());
    }
};