● 344.反转字符串
● 541. 反转字符串II
● 剑指Offer 05.替换空格
● 151.翻转字符串里的单词
● 剑指Offer58-II.左旋转字符串
344.反转字符串
题目链接：
https://leetcode.cn/problems/reverse-string/
思路：左右两头字符串交换就行。可以用for循环遍历一半，同时注意边界问题，可以举一个极端的例子套近边界测试。
代码：
class Solution {
public:
void reverseString(vector<char>& s) {
int len = s.size();
for(int i=0;i<len/2;i++)
{
char tmp = s[i];
s[i] = s[len-i-1];
s[len-i-1] = tmp;
}
}
};
541. 反转字符串II
题目链接：https://leetcode.cn/problems/reverse-string-ii/
思路：以2k为单位进行递增的，for函数里改为2k增加即可。
class Solution {
public:
string reverse(string &s, int start, int end)
{
end = end-1;
while(start<end)
{
char tmp =s[end];
s[end] = s[start];
s[start] = tmp;
start++;
end--;
}
return s;
}
string reverseStr(string s, int k) {
int len = s.length();
for(int i=0;i<len;i+=2*k)
{
if((i+k)<len)
{
reverse(s, i, i+k);
}
else
{
reverse(s, i, len);
}
}
return s;
}
};
剑指Offer 05.替换空格
题目链接：https://leetcode.cn/problems/ti-huan-kong-ge-lcof/
思路：
扩充字符串，从后往前遍历就不会被覆盖
class Solution {
public:
string replaceSpace(string s) {
string s2 = "";
int len = s.length();
int count_space = 0;
for(int i=0;i<len;i++)
{
if(s[i] == ' ')
{
count_space++;
}
}
int len2 = len + count_space*2;
s.resize(s.size() + count_space * 2);
for(int i=len-1;i>=0;i--)
{
if(s[i]==' ')
{
s[--len2] = '0';
s[--len2] = '2';
s[--len2] = '%';
}
else
s[--len2] = s[i];
}
return s;
}
};
151.翻转字符串里的单词
题目链接：https://leetcode.cn/problems/reverse-words-in-a-string/
思路：
首先使用移除字符串中相同元素的思路移除掉多余的空格
再反转整个字符串
然后反正单个字符串。
可以想把先把不同的情况归一成一种情况再解决问题。
代码：
class Solution {
public:
void reverse(string &s, int start, int end)
{
end--;
while(start<end)
{
char tmp = s[start];
s[start] = s[end];
s[end] = tmp;
start++;
end--;
}
}
string reverseWords(string s) {
int len = s.length();
//第一步，移除多余空格
int fast=0,slow=0;
while(fast<len)
{
if(s[fast]!=' ')
{
if(slow!=0)
{
s[slow] = ' ';
slow++;
}
while(fast<len && s[fast]!=' ')
{
s[slow] = s[fast];
slow++;
fast++;
}
}
else
fast++;
}
s.resize(slow);
reverse(s, 0, s.size());
int start=0;
for(int i=0; i<=s.size();i++)
{
if(s[i] == ' '||i==s.size())
{
reverse(s, start, i);
start = i+1;
}
}
return s;
}
};
剑指 Offer 58 - II. 左旋转字符串
题目：https://leetcode.cn/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/
核心思路：
其实可以把前n个字符当做一个work，剩下的字符是另一个word，那就可以使用前面一个题目的思想来解决问题。
代码：
class Solution {
public:
void reverse(string &s, int start, int end)
{
end--;
while(start<end)
{
char tmp = s[start];
s[start] = s[end];
s[end] = tmp;
start++;
end--;
}
}
string reverseLeftWords(string s, int n) {
int len = s.size();
reverse(s, 0, n);
reverse(s, n, len);
reverse(s, 0, len);
return s;
}
};
