前言
本组题目非常重要！！！！覆盖了字符串的基本操作，并涉及大量底层思想。
151. 反转字符串中的单词
给你一个字符串 s ，请你反转字符串中 单词 的顺序。
单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
注意： 输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
难点
- 不使用额外辅助空间
O(1) - 实现词间的翻转，需要进行单词而非仅仅字符的识别
- 尾随、前导以及词之间多余空格的移除
思路
- 遍历一趟去空格（
target=' '的移除元素）~ “快慢指针” 快指针找最终元素，慢指针记录最终位置：- 前导空格：全部删除，只要是
' '且不超过size()，快指针就++ - 词间空格：只留一个，有多余的
s[i-1] == s[i] == ' '，不计入慢指针 - 尾随空格：全部删除，自慢指针向后截断
- 前导空格：全部删除，只要是
- 然后整个字符串翻转(doog os)，再对每个单词做翻转(good so)
- reverse()函数的参数应该是迭代器，而不是字符：
reverse(s[start], s[i-1]);👎reverse(s.begin() + start, s.begin() + i);👍
代码实现
class Solution {
public:
void removeSpace(string &s){
int slowIndex = 0;
int fastIndex = 0;
while(fastIndex<s.size() && s[fastIndex]==' '){
fastIndex++;
}
for(;fastIndex<s.size(); fastIndex++){
if(fastIndex - 1 > 0 && s[fastIndex-1]==s[fastIndex] && s[fastIndex]==' '){
continue;
}
else{
s[slowIndex++] = s[fastIndex];
}
}
if(slowIndex - 1 > 0 && s[slowIndex-1] == ' '){
s.resize(slowIndex - 1);
}else{
s.resize(slowIndex);
}
}
string reverseWords(string s) {
removeSpace(s);
reverse(s.begin(), s.end());
int start = 0;
for(int i=0; i<=s.size(); i++){
if(i==s.size() || s[i]==' '){
reverse(s.begin() + start, s.begin() + i);
start = i+1;
}
}
return s;
}
};
55. 右旋字符串
字符串的 右旋转 操作是把字符串尾部的若干个字符转移到字符串的前面。给定一个字符串 s 和一个正整数 k，将字符串中的后面 k 个字符移到字符串的前面，实现字符串的右旋转操作。
例如，对于输入字符串 "abcdefg" 和整数 2，函数应该将其转换为 "fgabcde"。
重点！！！！！！
以 s='abcdef' 为例：
- 在划分右旋区间时要注意reverse()函数反转的区间是 左闭右开 区间！即[first,last)，
- 因此，
reverse(s.begin(), s.begin()+2)的结果为ba cdef
- 因此，
begin()指向第一个字符，end()则指向最后一个字符的 下一个 位置。s.begin()指向a的地址，*s.begin() = 'a's.end()指向g之后的一个位置，一个虚拟的\0，*(s.end()-1) = 'g'
思路
- 实现原地操作，如何将
abcdefg后n个字符挪到前面？- 首先，将字符串整体翻转：
'gfedcba' - 然后，将前
n个字符翻转：'fgedcba' - 最后，将后
size-n个字符翻转：'fgabcde'
- 首先，将字符串整体翻转：
代码实现
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int n;
string s;
cin >> n;
cin >> s;
int len = s.size();
reverse(s.begin(), s.end()); // 全部
reverse(s.begin(), s.begin()+n); // 左
reverse(s.begin()+n, s.end()); // 右
cout<< s;
}
尝试先局部翻转，再整体翻转：
reverse(s.begin(), s.end()-n); // 左
reverse(s.end()-n, s.end()); // 右
reverse(s.begin(), s.end()); // 全部
