题目描述

算法

(数组翻转) O(n)
- 此题不能读取这个字符串，所以无法用cin >> s去翻转每个单词，而且这样空间复杂度是O(n）
- 一步到位很难去做，我们可以通过操作分解来做
1. 将字符串的每个单词逆序 __ab_cde___fgh___ => ba_edc_hgf
2. 将整个字符串逆序ba_edc_hgf => fgh_cde_ab

时间复杂度

• 整个字符串总共扫描两遍，所以时间复杂度是O(n)，且空间复杂度为O(1)

C++代码

// time:O(n) space:O(1)
class Solution {
public:
    string reverseWords(string s) {
        int k = 0;
        // __ab_cde___fgh___ => ba_edc_hgf
        for (int i = 0; i < s.size();)
        {
            int j = i;
            while (j < s.size() && s[j] == ' ') j ++ ;
            if (j == s.size()) break; 
            i = j;
            while (j < s.size() && s[j] != ' ') j ++ ;
            reverse(s.begin() + i, s.begin() + j);

            // Reassign the s string
            if (k) s[k ++ ] = ' ';
            while (i < j) s[k ++ ] = s[i ++ ];
        }
        s.erase(s.begin() + k, s.end()); // Get rid of the excess length
        // ba_edc_hgf => fgh_cde_ab
        reverse(s.begin(), s.end());

        return s;
    }
};

附：reverse等价写法

for (int i = 0, j = s.size() - 1; i < j; i ++, j --) swap(s[i], s[j]);
// reverse(s.begin(), s.end());

找出来某个连续的一段（经典）

代码模版

for(int i = 0; i < n; i ++) {
    int j = i;
    while (j < n && ...) ...
    具体问题逻辑
}

例：原题链接

class Solution {
public:
    string reverseWords(string s) {
        reverse(s.begin(), s.end());

        int n = s.size();

        // 找出来某个连续的一段——非常经典
        for(int i = 0; i < n; i ++) {
            int j = i;
            while (j < n && s[j] != ' ') j ++;
            reverse(s.begin() + i, s.begin() + j);
            i = j; // i此时指向空格，后面会+1，找下一个连续段
        }

        return s;
    }
};