字符串|344.反转字符串、541. 反转字符串II、剑指Offer 05.替换空格、151.翻转字符串里的单词、剑指Offer58-II.左旋转字符串
344.反转字符串
自己审题思路
遍历字符串数组，然后交换
看完代码随想录题解后的收获
思路基本一致
代码：
class Solution {
public:
void swap(char* a, char* b) {
char tmp = *a;
*a = *b;
*b = tmp;
}
void reverseString(vector<char>& s) {
int n = s.size();
for(int i = 0; i < n/2; i++) {
swap(&s[i], &s[n - i -1]);
}
}
};
/* 引用
class Solution {
public:
void swap(char& a, char& b) {
char tmp = a;
a = b;
b = tmp;
}
void reverseString(vector<char>& s) {
int n = s.size();
for(int i = 0; i < n/2; i++) {
swap(s[i], s[n - i -1]);
}
}
};
*/
这里需要注意，
swap()函数形参如果使用int&或者 int* 会报错，虽然字符可以转化成其ASCII码，但是这里类型不匹配还是会报错。
就算可以进行类型转换，这里也会报错，因为如果试图将一个临时对象绑定在非reference to const类型的reference上，那么编译器会给出错误。
参考
参考详解
541. 反转字符串II
自己审题思路
前一个算法题的进阶，处理好2k中的前k个和最后不多于k个的情况是个难点
看完代码随想录题解后的收获
遍历字符串的过程中，只要让 i += (2 * k)，i 每次移动 2 * k 就可以了，然后判断是否需要有反转的区间。这样方便很多，后续只需要判断剩余字符串长度是否大于k，大于k翻转前k个，小于k全部翻转。
代码：
class Solution {
public:
// void reverse(vector<char>& s) {
// int n = s.size() -1;
// for (int i = 0; i < s.size() / 2; i++) {
// swap(s[i], s[n - i]);
// }
// }
string reverseStr(string s, int k) {
// vector<char> str(s.begin(), s.end());
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.替换空格
自己审题思路
第一时间想到双指针，但是从前往后比较麻烦，每次遇到空格都需要移动空格后面的所有元素
看完代码随想录题解后的收获
数组填充类的问题，都可以先预先给数组扩容带填充后的大小，然后再从后向前进行操作。
代码：
class Solution {
public:
string replaceSpace(string s) {
int size = s.size();
int count = 0; // 统计空格的个数
for (int i = 0; i < size; i++) {
if (s[i] == ' ') {
count++;
}
}
int oldSize = s.size();
s.resize(size + 2 * count); // 根据空格个数扩充字符串
int newSize = s.size();
// 从后往前将空格替换为"%20"
for (int i = oldSize, j = newSize; i < j;i--, j-- ) {
if (s[i] != ' ') {
s[j] = s[i];
} else {
s[j] = '0';
s[j - 1] = '2';
s[j - 2] = '%';
j -= 2;
}
}
return s;
}
};
参考详解
151.翻转字符串里的单词
自己审题思路
这道题初拿到没有什么思路
看完代码随想录题解后的收获
题解思路：
1、删除多余空格
2、反转整个字符串（难点）
3、反转每个单词
循环里处理了某个参数，就需要在循环判断里额外判断一下这个参数，避免越界
// 去掉字符串前面的空格
while (s.size() > 0 && fastIndex < s.size() && s[fastIndex] == ' ') {
fastIndex++;
}
代码：
/*
*1、删除多余空格
*2、反转整个字符串
*3、反转每个单词
*/
class Solution {
public:
void reverse(string& s, int start, int end) {//左闭右开
for (int i = start, j = end - 1; i < j; i++,j--) {
swap(s[i], s[j]);
}
}
void delSpace(string& s) {
int slow = 0;
int fast = 0;
for (; fast < s.size();fast++) {
if (s[fast] != ' ') {
if (slow != 0) s[slow++] = ' ';//手动控制空格，给单词之间添加空格。slow != 0说明不是第一个单词，需要在单词前添加空格。
while (fast < s.size() && s[fast] != ' ') {
s[slow++] = s[fast++];
}
}
}
s.resize(slow);
}
string reverseWords(string s) {
int count = 0; // 记录空格的下一个元素（即下一个字符的开始位置）
delSpace(s);
reverse(s, 0, s.size());
for (int i = 0; i <= s.size(); i++) {
if (i == s.size() || s[i] == ' ') { // if (s[i] == ' ') 这里这么写字符串尾最后一个单词不会翻转
reverse(s, count, i); // reverse(s, count + 1, i); count = i; 这里这么写第一个字符不会被翻转
count = i + 1;
}
}
return s;
}
};
参考详解
剑指Offer58-II.左旋转字符串
自己审题思路
申请一个新的数组，不包含前n个元素，然后将前n个元素依次插到数组后面。
代码：
class Solution {
public:
string reverseLeftWords(string s, int n) {
vector<char> str(s.begin() + n, s.end());
for (int i = 0; i < n; i++) {
str.emplace_back(s[i]);
}
return std::string(str.begin(), str.end());
}
};
看完代码随想录题解后的收获
不申请额外空间的思路：
1、反转区间为前n的子串
2、反转区间为n到末尾的子串
3、反转整个字符串
代码
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;
}
};
参考详解
今日感悟：
字符串翻转和替换优先想到双指针
