今日任务
- 反转字符串
- 反转字符串II
- 剑指Offer 05.替换空格
- 翻转字符串里的单词
- 剑指Offer58-II.左旋转字符串
详细布置
344.反转字符串
建议： 本题是字符串基础题目，就是考察 reverse 函数的实现，同时也明确一下 平时刷题什么时候用 库函数，什么时候 不用库函数
题目链接/文章讲解/视频讲解：https://programmercarl.com/0344.%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2.html
Tips：很简单的双指针法，这里可以用swap库函数让代码更加直观。
我的题解：
class Solution {
public:
void reverseString(vector<char>& s) {
int left = 0;
int right = s.size() - 1;
while(left<right){
swap(s[left], s[right]);
left++;
right--;
}
}
};541. 反转字符串II
建议：本题又进阶了，自己先去独立做一做，然后在看题解，对代码技巧会有很深的体会。
题目链接/文章讲解/视频讲解：https://programmercarl.com/0541.%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2II.html
Tips：
1. 这道题中，因为reverse只是其中的一个小步骤，并不是题目考察重点，因此可以使用库函数来实现。（再加上刚在上一题中写过一次了）
2. 这道题的巧妙之处在于，通过每次将i = i + 2k这种方式来移动指针，就能够巧妙地解决题设条件里的问题。
我的题解：
class Solution {
public:
string reverseStr(string s, int k) {
for(int i = 0; i< s.size(); i+= 2*k ){
if(i + k <= s.size()){
reverse(s.begin() + i, s.begin() + i + k);
}
else{
reverse(s.begin() + i, s.end());
}
}
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
Tips：这道题用双指针的解法比较极限了，其实如果不是那么在意空间复杂度的话，可以声明一个新字符串来做这件事。
我的题解：
class Solution {
public:
string replaceSpace(string s) {
int newSize = s.size();
int oldSize = s.size();
for(int i = 0; i<s.size();i++){
if(s[i] == ' '){
newSize += 2;
}
}
s.resize(newSize);
int oldP = oldSize -1;
int newP = newSize -1;
while(newP>=0){
if(s[oldP]!=' '){
s[newP] = s[oldP];
}
else{
s[newP] = '0';
s[--newP] = '2';
s[--newP] = '%';
}
newP--;
oldP--;
}
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
Tips：这个题题解是纯自己写的，思路就是用栈和substr完成操作，其实还可以用split库函数
我的题解：
class Solution {
public:
string reverseWords(string s) {
//第一反应是用栈和substr
stack<string> words;
for(int i=0;i<s.size();i++){
while(i<s.size() && s[i] == ' '){
i++;
}
if(i >= s.size()){
break;
}
int j = i;
while(j < s.size() && s[j] != ' '){
j++;
}
words.push(s.substr(i,j-i));
i = j;
}
string result;
while(!words.empty()){
result += words.top();
words.pop();
if(!words.empty()){
result += " ";
}
}
return result;
}
};Tips2：如果不采用辅助空间，空间复杂度要求为O(1)的话，题解如下
我的题解：
class Solution {
public:
string reverseWords(string s) {
//这是不使用辅助空间，空间复杂度要求为O(1)的题解
removeSpaces(s);
reverse(s.begin(), s.end());
for(int i = 0; i< s.size();i++){
int j = i;
while(j < s.size() && s[j]!=' '){
j++;
}
//reverse库函数是左闭右开区间，反转的时候不包括区间右端点
reverse(s.begin() + i, s.begin() + j);
// 因为在for循环那里i还要+1，所以这里i = j就行
i = j;
}
return s;
}
void removeSpaces(string& s){
int slow = 0;
for(int i =0; i<s.size();i++){
if(s[i]!=' '){
if(slow!=0){
s[slow++] = ' ';
}
// 下面这个while循环其实可以去掉
// 在这里写了是因为可以省去一些判断，但时间复杂度是一样的
while(i< s.size()&& s[i]!=' '){
s[slow++] = s[i++];
}
}
}
s.resize(slow);
}
};剑指Offer58-II.左旋转字符串
建议：题解中的解法如果没接触过的话，应该会想不到
Tips：在原题条件下，用substr解决
我的题解：
class Solution {
public:
string reverseLeftWords(string s, int n) {
string left = s.substr(0,n);
string right = s.substr(n,s.size());
return right +left;
}
};Tips：为了让本题更有意义，提升一下本题难度：不能申请额外空间，只能在本串上操作。
我的题解：
具体步骤为：
- 反转区间为前n的子串
- 反转区间为n到末尾的子串
- 反转整个字符串
最后就可以达到左旋n的目的，而不用定义新的字符串，完全在本串上操作。
例如 ：示例1中 输入：字符串abcdefg，n=2
如图：
最终得到左旋2个单元的字符串：cdefgab
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;
}
};