今日刷题5道，开始字符串部分：344.反转字符串， 541. 反转字符串II， 剑指Offer 05.替换空格，151.翻转字符串里的单词，剑指Offer58-II.左旋转字符串。
● 344.反转字符串
题目链接/文章讲解/视频讲解：https://programmercarl.com/0344.%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2.html
ps:比较简单，和数组的思想一样，用双指针解决，这里涉及两个库函数，一个是reverse()函数，直接实现本题，一个是swap()函数，作为两数交换。
如果题目关键的部分直接用库函数就可以解决，建议不要使用库函数。
如果库函数仅仅是 解题过程中的一小部分，并且你已经很清楚这个库函数的内部实现原理的话，可以考虑使用库函数。
class Solution { public: void reverseString(vector<char>& s) { for(int i=0;i<s.size()/2;i++){ int j = s.size() - i -1; char temp = s[i]; s[i] = s[j]; s[j] = temp; } } };● 541. 反转字符串II
题目链接/文章讲解/视频讲解：https://programmercarl.com/0541.%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2II.html
碎碎念：这个题也太绝了，卡哥视频里说的所有坑都踩了，然而实现起来是这么简单，真的栓q。对了，一般系统里的库函数都是左闭右开的。
class Solution {
public:
string reverseStr(string s, int k) {
for (int i = 0; i < s.size(); i += (2 * k)) {
// 1. 每隔 2k 个字符的前 k 个字符进行反转
// 2. 剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符
if (i + k <= s.size()) {
reverse(s.begin() + i, s.begin() + i + k );
} else {
// 3. 剩余字符少于 k 个，则将剩余字符全部反转。
reverse(s.begin() + i, s.end());
}
}
return s;
}
};我们也可以实现自己的reverse函数：
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]);
}
}
string reverseStr(string s, int k) {
for (int i = 0; i < s.size(); i += (2 * k)) {
// 1. 每隔 2k 个字符的前 k 个字符进行反转
// 2. 剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符
if (i + k <= s.size()) {
reverse(s, i, i + k - 1);
continue;
}
// 3. 剩余字符少于 k 个，则将剩余字符全部反转。
reverse(s, i, s.size() - 1);
}
return s;
}
};● 剑指Offer 05.替换空格
题目链接/文章讲解：https://programmercarl.com/%E5%89%91%E6%8C%87Offer05.%E6%9B%BF%E6%8D%A2%E7%A9%BA%E6%A0%BC.html
ps:若替换后的长度发生变化，需要先更改size大小，再从后往前进行替换。
class Solution { public: string replaceSpace(string s) { int count=0; int oldsize=s.size(); for(int i=0;i<s.size();i++){ if(s[i]==' '){ count++; } } s.resize(s.size() + count * 2); int newsize = s.size(); for(int i=newsize-1, j = oldsize - 1 ; j<i ; i--,j--){ if(s[j]!=' '){ s[i]=s[j]; } else{ s[i]='0'; s[i-1]='2'; s[i-2]='%'; i-=2; } } return s; } };● 151.翻转字符串里的单词
题目链接/文章讲解/视频讲解：https://programmercarl.com/0151.%E7%BF%BB%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2%E9%87%8C%E7%9A%84%E5%8D%95%E8%AF%8D.html
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; //整体思想参考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的大小即为去除多余空格后的大小。
}
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;
}
};● 剑指Offer58-II.左旋转字符串
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;
}
};