字符串也可以理解成一种数组，然后定义前后两个指针，同时向中间移动并交换元素
class Solution {
public:
void reverseString(vector& s) {
for (int left = 0, right = s.size() - 1; left < right; left++, right--) { //条件也可以改成left<.size()/2 遍历到字符串的一半就可以返回结果
swap(s[left], s[right]);
}
}
};
题目2：541.反转字符串Ⅱ
解法：模拟
反转每个下标从 2k2k 的倍数开始的，长度为 kk 的子串。若该子串长度不足 kk，则反转整个子串。
class Solution {
public:
string reverseStr(string s, int k) {
for (int i = 0; i < s.size(); i += (2 * k)) { //使用+=让i每次移动2k，然后判断是否反转
if (i + k <= s.size()) { //1.每隔2k个字符的前k个字符进行反转 2.剩余字符小于2k但大于或等于k个，则反转前k个字符
reverse(s.begin() + i, s.begin() + i + k); //reverse()会将区间[beg,end)内的元素全部逆序
continue; //直接进入下一轮循环
}
reverse(s.begin() + i, s.begin() + s.size()); //3.剩余字符少于 k 个，则将剩余字符全部反转
}
return s;
}
};
官方给出的代码更加简洁：
class Solution {
public:
string reverseStr(string s, int k) {
int n = s.length();
for (int i = 0; i < n; i += 2 * k) {
reverse(s.begin() + i, s.begin() + min(i + k, n));
}
return s;
}
};
题目3：剑指Offer05.替换空格
解法：双指针法
解题思路：
将空格变成%20(一个字符变成三个字符)，因此可以将字符串的大小resize，然后遍历字符串将空格替换成%20
如果从前向后填充，时间复杂度就变成了O(n2)，因为每次添加元素都要将添加元素之后的所有元素向后移动。
class Solution {
public:
string replaceSpace(string s) {
int count = 0; //空格数
int oldsize = s.size(); //替换前的字符串长度
for (int i = 0; i < oldsize; i++) { //统计字符串中的空格数
if (s[i] == ' ') {
count++;
}
}
s.resize(s.size() + 2*count); //扩充字符串
int newsize = s.size(); //扩充后字符串长度
//从后向前将空格替换为%20
for (int i = newsize-1, j = oldsize-1; j < i; i--, j--) { //i指向新长度的末尾，j指向旧长度的末尾
if (s[j] != ' ') {
s[i] = s[j];
}
else {
s[i] = '0';
s[i - 1] = '2';
s[i - 2] = '%';
i -= 2;
}
}
return s;
}
};
评论区大佬用了字符数组的解法，非常的巧妙：
与双指针法相比，双指针法是在原来的字符串中进行改动，字符数组是重新创建了一个新的数组
class Solution {
public:
string replaceSpace(string s) { //字符数组
string array; //存储结果
for(auto &c : s){ //遍历原字符串
if(c == ' '){
array.push_back('%');
array.push_back('2');
array.push_back('0');
}
else{
array.push_back(c);
}
}
return array;
}
};
题目4：151.颠倒字符串中的单词
解法一：双指针法
根据代码随想录的解题思路：
先移除多余的空格，如" the sky is blue "变成"the sky is blue"；
然后将整个字符串翻转，"eulb si yks eht"；
最后再将单词进行翻转，"blue is sky the"。
//版本一
class Solution {
public:
// 反转字符串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]);
}
}
// 移除冗余空格：使用双指针（快慢指针法）O(n)的算法
void removeExtraSpaces(string& s) {
int slowIndex = 0, fastIndex = 0; // 定义快指针，慢指针
// 去掉字符串前面的空格
while (s.size() > 0 && 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) {
removeExtraSpaces(s); // 去掉冗余空格
reverse(s, 0, s.size() - 1); // 将字符串全部反转
int start = 0; // 反转的单词在字符串里起始位置
int end = 0; // 反转的单词在字符串里终止位置
bool entry = false; // 标记枚举字符串的过程中是否已经进入了单词区间
for (int i = 0; i < s.size(); i++) { // 开始反转单词
if (!entry) {
start = i; // 确定单词起始位置
entry = true; // 进入单词区间
}
// 单词后面有空格的情况，空格就是分词符
if (entry && s[i] == ' ' && s[i - 1] != ' ') {
end = i - 1; // 确定单词终止位置
entry = false; // 结束单词区间
reverse(s, start, end);
}
// 最后一个结尾单词之后没有空格的情况
if (entry && (i == (s.size() - 1)) && s[i] != ' ') {
end = i;// 确定单词终止位置
entry = false; // 结束单词区间
reverse(s, start, end);
}
}
return s;
}
先根据版本一理解解题思路和过程，再看更加精简的版本二：
版本二
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; //整体思想参考Leetcode: 27. 移除元素：https://leetcode-cn.com/problems/remove-element/
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的大小即为去除多余空格后的大小。
}
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;
}
};
解法二：双端队列
官方提供了一种双端队列的方法，即[deque容器
C++ STL deque容器（详解版）
沿着字符串一个一个单词处理，然后将单词压入队列的头部，再将队列转成字符串即可。
class Solution {
public:
string reverseWords(string s) {
int left = 0, right = s.size() - 1;
// 去掉字符串开头的空白字符
while (left <= right && s[left] == ' ') ++left;
// 去掉字符串末尾的空白字符
while (left <= right && s[right] == ' ') --right;
deque d;
string word;
while (left <= right) {
char c = s[left];
if (word.size() && c == ' ') {
// 将单词 push 到队列的头部
d.push_front(move(word));
word = "";
}
else if (c != ' ') {
word += c;
}
++left;
}
d.push_front(move(word));
string ans;
while (!d.empty()) {
ans += d.front();
d.pop_front();
if (!d.empty()) ans += ' ';
}
return ans;
}
};
题目5：剑指Offer58.II.左旋转字符串
解法一：字符串切分与拼接
解题思路：
获取str[n:] 和 str[:n]子串，目标串target = str[:n] + str[n:];
class Solution {
public:
string reverseLeftWords(string s, int n) {
string str1 = s.substr(0, n); //str[:n]
string str2 = s.substr(n, s.size() - n); //str[n:]
string newstr = str2 + str1;
return newstr;
}
};
解法二：翻转
解题思路：
通过局部翻转+整体翻转达到左旋转的目的，不需要定义新的字符串，完全在原字符串上操作
首先翻转str[:n]子串，其次翻转str[n:]子串，最后翻转str.
class Solution {
public:
string reverseLeftWords(string s, int n) {
reverse(s.begin(), s.begin() + n); //翻转区间前n的子串
reverse(s.begin() + n, s.end()); //翻转区间n到末尾的子串
reverse(s.begin(), s.end()); //翻转整个字符串
return s;
}
};
