(C++字符串02) 反转字符串中的单词

151、反转字符串中的单词

先将字符串的里的多余空格去掉，时间复杂度:O(n)，再将字符串整体反转，时间复杂度:O(n)，最后反转每一个单词，时间复杂度:O(n)；

class Solution {
public:string reverseWords(string s) {removeExtraSpaces(s);swap(s, 0, s.size() - 1);int left = 0;for(int right = 0; right <= s.size(); right++) {if(s[right] == ' ' || right == s.size()) {swap(s, left, right-1);left = right + 1;}}return s;}void removeExtraSpaces(string& s) {int slow = 0;for(int i = 0; i < s.size(); i++) {if(s[i] != ' ') {if(slow != 0) {s[slow++] = ' ';}while(i < s.size() && s[i] != ' ') {s[slow++] = s[i++];}}}s.resize(slow);}void swap(string& s, int left, int right) {for(; left < right; left++, right--) {char tem = s[left];s[left] = s[right];s[right] = tem;}}
};

时间复杂度：O(n)

空间复杂度：O(1)

55. 右旋字符串(卡码网)

408考过这个，局部反转外加整体反转可以实现字符串的旋转操作

#include<iostream>
using namespace std;
void reverse(string& s, int left, int right);
int main() {int n;string s;cin >> n;cin >> s;reverse(s, 0, s.size() - 1);reverse(s, 0, n - 1);reverse(s, n, s.size() - 1);cout << s << endl;
}
void reverse(string& s, int left, int right) {for(; left < right; left++, right--) {char tem = s[left];s[left] = s[right];s[right] = tem;}
}

时间复杂度：O(n)

空间复杂度：O(1)