05.替换空格
题目链接：05.替换空格
题目描述：请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
示例 1： 输入：s = "We are happy."
输出："We%20are%20happy."
思路
本题最好不要使用额外的辅助空间
- 首先扩充数组到每个空格替换成"%20"之后的大小
- 然后从后向前替换空格，也就是双指针法
- i指向新长度的末尾，j指向旧长度的末尾
其实很多数组填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作。
好处：不用申请数组； 避免了从前往后填充元素时，每次都要添加元素时要向后移动所有元素。
代码实现
//替换空格
//首先扩充数组到每个空格替换成"%20"之后的大小。
//然后从后向前替换空格，也就是双指针法，
class Solution{
public:
string replaceSpace(string s){
int count = 0;
int s0ldsize = s.size();
for(int i = 0; i < s.szie(); i++){
if(s[i] == ''){
count++;//如果遍历到空格，count空格数加一
}
}
s.resize(s.size() + count * 2);//扩充字符串s的大小，也就是每个空格替换成"%20"之后的大小
int sNewSize = s.size();
for(int i = sNewSize - 1, j = s0ldSize - 1; j<i; i--;j--){
// int i = sNewSize - 1, j = s0ldSize - 1即i指向新长度的末尾，j指向旧长度的末尾
if(s[j] != ''){
s[i] = s[j]; //不是空格时，j的位置赋值给i j不变（即前面的给后面的）
}else {//如果s[j]是空格时，填上%20，注意位置
s[i] = '0';
s[i - 1] = '2';
s[i - 2] = '%';
i -= 2;
}
}
return s;
151.翻转字符串里的单词
题目链接：151.翻转字符串里的单词
题目描述：给定一个字符串，逐个翻转字符串中的每个单词。
示例 1：
输入: "the sky is blue"
输出: "blue is sky the"
示例 2：
输入: " hello world! "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例 3：
输入: "a good example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
思路
不适用辅助空间，那么只能在原字符串上下手：想一下，我们将整个字符串都反转过来，那么单词的顺序指定是倒序了，只不过单词本身也倒序了，那么再把单词反转一下，单词不就正过来了。
- 移除多余空格（这是本题的难点，所以不应该使用库函数解决）
- 将整个字符串反转（此时可以使用库函数解决）
- 每个单词反转
代码实现
//151.翻转字符串里的单词--双指针法
void removeExtraSpaces(string& s){
int slowIndex = 0, fastIndex = 0; // 定义快指针，慢指针,都指向起始位置
for(; fast < s.size(); fast++ ) {
if(s[fast] != '') {//把不为空的字符收集起来
// 有一个逻辑需要特殊处理一下，即首单词前不需要空格
if(slow != '') s[slow++] = ' ';//slow++只是写进里面去了
//这一段是一个整体，即慢指针不是起始位置的时候，你的满指针所指向的位置要多留出一个空格
if(fast < s.size() && s[fast] != ''){//注意条件不要大于s长度斌且fast不为空时
s[slow] = s[fast];//将快指针指向的单词赋值给慢指针
fast++;
slow++;
}
}
s.resize(slow);//因为是原地修改字符串，新的字符串是slow指向的位置
}
}
.左旋转字符串
题目链接：左旋转字符串、
题目描述：字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。
示例 1：
输入: s = "abcdefg", k = 2
输出: "cdefgab"
示例 2：
输入: s = "lrloseumgh", k = 6
输出: "umghlrlose"
思路
还是一样不能申请额外空间，只能在本串上进行操作。
但其实和上一题的解法类似，整体反转＋局部反转就可以实现反转单词顺序的目的。
- 反转区间为前n的子串
- 反转区间为n到末尾的子串
- 反转整个字符串
- 如图所示：
代码展示
//题目：剑指Offer58-II.左旋转字符串
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;
}
};
总结
-
反转字符串第一次讲到反转一个字符串应该怎么做，使用了双指针法。
-
然后发现541. 反转字符串II，这里开始给反转加上了一些条件，当需要固定规律一段一段去处理字符串的时候，要想想在for循环的表达式上做做文章。
-
后来在151.翻转字符串里的单词 ，要对一句话里的单词顺序进行反转，发现先整体反转再局部反转 是一个很妙的思路。
-
最后，本题则是先局部反转再 整体反转，与151.翻转字符串里的单词 (opens new window)类似，但是也是一种新的思路。