目录
反转字符串
原理：
对于字符串在原地翻转问题，可以reverse。但是其本质我们可以知道是利用双指针方法。一个指向开始，一个指向结束，不断交换两个指针的值，这里交换可以用swap，或者中间变量交换。
代码如下：
class Solution {
public:
void reverseString(vector<char>& s) {
int left = 0;
int right = s.size() - 1;
char temp;
while (left < right)
{
swap(s[left],s[right]);
left++;
right--;
}
}
};相关题目：
344. 反转字符串 - 力扣（LeetCode）
https://leetcode.cn/problems/reverse-string/541. 反转字符串 II - 力扣（LeetCode）https://leetcode.cn/problems/reverse-string-ii/
替换空格
方法：
我们主要是先计算出扩充之后的大小，以及从后遍历数组解决数据不移动问题。
统计需要扩充的大小
int count = 0;
int oldWidth = s.size();
for(int i = 0; i < s.size(); i++){
if(s[i] == ' '){
count++;
}
}
int newWidth = s.size() + count * 2;
s.resize(newWidth);定义两个指针，一个是旧数组末尾，一个是新数组末尾。如果不是空格，两个同时--。当遇到空格，新指针一次性移动三位，并且填充三位。
//从后往前遍历
for(int i = oldWidth - 1, j = newWidth - 1; i < j; j--, i--){
if(s[i] != ' '){
s[j] = s[i];
}
else{
s[j] = '0';
s[j - 1] = '2';
s[j - 2] = '%';
j -= 2;
}完整代码：
class Solution {
public:
string replaceSpace(string s) {
int count = 0;
int oldWidth = s.size();
for(int i = 0; i < s.size(); i++){
if(s[i] == ' '){
count++;
}
}
int newWidth = s.size() + count * 2;
s.resize(newWidth);
//从后往前遍历
for(int i = oldWidth - 1, j = newWidth - 1; i < j; j--, i--){
if(s[i] != ' '){
s[j] = s[i];
}
else{
s[j] = '0';
s[j - 1] = '2';
s[j - 2] = '%';
j -= 2;
}
}
return s;
}
};相关题目：
剑指 Offer 05. 替换空格 - 力扣（LeetCode）https://leetcode.cn/problems/ti-huan-kong-ge-lcof/
翻转字符串里的单词
方法：
思路为：去除空格，翻转字符串，对每个单词再进行翻转。
去除空格：双指针实现。首先遍历整个字符串。当遇到非‘ ’时，把快指针遍历的元素插入慢指针对应的下标。
注意：我们对于中间的单词是需要空格的，因此我们会在不是第一个起始位置的地方插入一个空格，然后开始后续的插入非空格元素。
翻转字符串：遍历字符串，利用swap进行交换
单词翻转：利用计数器。遍历整个字符串，当计数器遇到单词边界或者字符串边界时，翻转计数器对应的单词。然后更新计数器，继续找下一个单词。
整个代码如下：
class Solution {
public:
void reverse(string& s, int start, int end){ //翻转，区间写法：左闭又闭 []
for(int i = start, j = end; i < j; i++, j--){
swap(s[i], s[j]);
}
}
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++];
}
}
}
return s.resize(slow);
}
string reverseWords(string s) {
removeExtraSpaces(s);//去除空格
reverse(s, 0, s.size()-1);//翻转
//翻转单词
int start = 0;
for(int i = 0; i <= s.size(); i++){
if(i == s.size() || s[i] == ' '){
//当i移动到边界或者碰到单词边界
reverse(s, start, i - 1);
start = i + 1;
}
}
return s;
}
};相关题目：
151. 反转字符串中的单词 - 力扣（LeetCode）https://leetcode.cn/problems/reverse-words-in-a-string/
左旋字符串
方法：
按照上图进行翻转即可。
class Solution {
public:
string reverseLeftWords(string s, int n) {
reverse(s.begin(), s.begin() + n);
reverse(s.begin() + n , s.end());//左闭右开
reverse(s.begin(), s.end());
return s;
}
};KMP
写起来很麻烦，算了，不写了！！！