151.翻转字符串里的单词

题目链接
状态：一遍过
思路：使用栈，先进后出，除去空格

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    string reverseWords(string s) {
        stack<string> stack;
        int n=s.size();
        for(int i=0;i<n;i++){
            string tmp;
            while(i<n&&s[i]!=' '){
                tmp+=s[i++];
            }
            if(tmp!=""){
                stack.push(tmp);
            }
        }
        string ans = stack.top();
        stack.pop();
        while(!stack.empty()){
            ans+=' ';
            ans+=stack.top();
            stack.pop();
        }
        return ans;

    }
};

官解思路：1.移除多余空格->2.将整个字符串反转->3.将每个单词反转
1.移除多余空格

1
2
3
4
5
6
7
8
9
10
11
12
void removeExtraSpaces(string& s) {//去除所有空格并在相邻单词之间添加空格, 快慢指针。
    int slow = 0;   //整体思想参考https://programmercarl.com/0027.移除元素.html
    for (int i = 0; i < s.size(); ++i) { //
        if (s[i] != ' ') { //遇到非空格就处理，即删除所有空格。
            if (slow != 0) s[slow++] = ' '; //手动控制空格，给单词之间添加空格。slow != 0说明不是第一个单词，需要在单词前添加空格。
            while (i < s.size() && s[i] != ' ') { //补上该单词，遇到空格说明单词结束。
                s[slow++] = s[i++];
            }
        }
    }
    s.resize(slow); //slow的大小即为去除多余空格后的大小。
}

2.将整个字符串反转
1
2
3
4
5
6
// 反转字符串s中左闭右闭的区间[start, end]
void reverse(string& s, int start, int end) {
    for (int i = start, j = end; i < j; i++, j--) {
        swap(s[i], s[j]);
    }
}

3.将每个单词反转

1
2
3
4
5
6
7
8
9
10
11
12
string reverseWords(string s) {
        removeExtraSpaces(s); //去除多余空格，保证单词之间之只有一个空格，且字符串首尾没空格。
        reverse(s, 0, s.size() - 1);
        int start = 0; //removeExtraSpaces后保证第一个单词的开始下标一定是0。
        for (int i = 0; i <= s.size(); ++i) {
            if (i == s.size() || s[i] == ' ') { //到达空格或者串尾，说明一个单词结束。进行翻转。
                reverse(s, start, i - 1); //翻转，注意是左闭右闭 []的翻转。
                start = i + 1; //更新下一个单词的开始下标start
            }
        }
        return s;
    }

总结：思路值得研究！

卡码网：55.右旋转字符串

题目链接
状态：一遍过
思路：经典三次旋转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <string>
using namespace std;

void reverse(string& s, int start, int end) {
    for (int i = start, j = end; i < j; i++, j--) {
        swap(s[i], s[j]);
    }
}

int main(){
    int k;
    string s;
    cin>>k>>s;
    int n=s.size();
    reverse(s,0,n);
    reverse(s,0,k);
    reverse(s,k,n);
    cout<<s;
}

还可以直接调库函数

1
2
3
4
5
6
#include<algorithm>
...
    reverse(s.begin(), s.end()); // 整体反转
    reverse(s.begin(), s.begin() + n); // 先反转前一段，长度n
    reverse(s.begin() + n, s.end()); // 再反转后一段
...

下面较难先占坑，以后回头填

28. 实现 strStr() （本题可以跳过）

题目链接

459.重复的子字符串 （本题可以跳过）

题目链接