leetcode151 反转字符串中的单词

其实就是整体反转，再局部反转，反反得正，最后就解出来了。

1. 去除多余空格。

2. 反转整个字符串。

3. 反转每个单词。

1.

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

    string reverseWords(string s) {
        int n = s.size();
        while(s[0] == ' '){
            s.erase(s.begin());
            n--;
        }
        while(s[n-1] == ' '){
            s.erase(n-1);
            n--;
        }
        for(int i = 0; i < n-1; i++){
            while(s[i] == ' ' && s[i+1] == s[i]){
                s.erase(i, 1);
                n--;
            }
        }

        reverse(s, 0, n-1);
        int start = 0;
        for(int i = 0; i <= n; i++){
            if(i == n || s[i] == ' '){
                reverse(s, start, i-1);
                start = i + 1;
            }
        }
        return s;
        }  
};

想一下真正的时间复杂度是多少，一个erase本来就是O(n)的操作。

erase操作上面还套了一个for循环，那么以上代码移除冗余空格的代码时间复杂度为O(n^2)。

2.快慢指针法

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


    string reverseWords(string s) {
        int n = s.size();
        int slow = 0, fast = 0;
        while(s[fast] == ' ') fast++;
        for(; fast < n; fast++){
            if(fast-1 > 0 && s[fast] == ' ' && s[fast-1] == s[fast]){
                continue;
            }
            s[slow++] = s[fast];
        }

        if(slow - 1 > 0 && s[slow-1] == ' '){
            s.resize(slow-1);
        }else{
            s.resize(slow);
        }

        n = s.size();

        reverse(s, 0, n-1);

        int start = 0;
        for(int i = 0; i <= n; i++){
            if(i == n || s[i] == ' '){
                reverse(s, start, i-1);
                start = i + 1;
            }
        }

        return s;
        }  
};

string.resize(2);尺寸变小，改变为2，多余字符被截掉了

str3.resize(10,'b');尺寸变大，可以给一个填充参数。尺寸由6变大到10，4个空位填充b(默认参数为0，即NULL或者'\0')。

删除多余空格后不要忘记重新计算n!!!

3.有、乱除非背下来估计想不好

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

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

    string reverseWords(string s) {
        
        
        removeExtraSpaces(s);
        int n = s.size();
        reverse(s, 0, n-1);

        int start = 0;
        for(int i = 0; i <= n; i++){
            if(i == n || s[i] == ' '){
                reverse(s, start, i-1);
                start = i + 1;
            }
        }

        return s;
        }  
};

代码随想录