摘要
- 快慢指针法，双指针法：fast 遍历原数组，slow 在原地构造我们需要的数组。
- 分治、分解的思想：左旋转字符串、翻转字符串里的单词，都可以分解为几个整体和局部的翻转。
今日学习的视频和文章
- 代码随想录 字符串基础
- C++Primer 字符串部分
- 代码随想录 反转字符串
- 代码随想录 反转字符串II
- 代码随想录 剑指Offer 05.替换空格
- 代码随想录 151.翻转字符串里的单词
- 代码随想录 剑指Offer58-II.左旋转字符串
LeetCode344 反转字符串
- 初见题目的想法：
- 双指针法，
left从最小下标开始，right从最大下标开始。不断交换s[left]和s[right]，右移left，左移right直到left >= right
- 双指针法，
初见题目的题解
class Solution {
public:
void reverseString(vector<char>& s) {
int n = s.size();
int left = 0;
int right = n - 1;
while (left < right) {
char temp = s[left];
s[left++] = s[right];
s[right--] = temp;
}
}
};
看了讲解之后，改用for语句使代码更加简洁
class Solution {
public:
void reverseString(vector<char>& s) {
for (int l = 0, r = s.size() - 1; l < r; l++, r--) {
swap(s[l], s[r]);
}
}
};
LeerCode541 反转字符串II
- 初见题目的想法：分治的思想，尝试将待反转的字符串分为长度为
2k的若干个子字符串，然后反转这些子字符串的前k个字符。
不使用STL库函数的题解，这里取[left, right]左闭右闭区间。
class Solution {
public:
string reverseStr(string s, int k) {
int n = s.size();
int count = 0;
for (int i = 0; i < n; i += 2 * k) {
int left = i;
int right = i + k - 1 < n ? i + k - 1: n - 1;
while (left < right) {
char temp = s[left];
s[left++] = s[right];
s[right--] = temp;
}
}
return s;
}
};
使用STL库函数的题解，注意迭代器的使用，迭代器严格遵守左闭右开区间[begin, end)
class Solution {
public:
string reverseStr(string s, int k) {
int n = s.size();
int count = 0;
for (int i = 0; i < n; i += 2 * k) {
int right = i + k;
reverse(s.begin() + i, right < n ? s.begin() + right : s.end());
}
return s;
}
};
LeetCode 剑指Offer.05 替换空格
- 初见题目的想法：
- 如果按顺序从左到右遍历，并且新开一个字符串来保存替换空格后的字符串，虽然时间复杂度也是
O(n)，但空间复杂度为O(n)；应该有更好的办法将空间复杂度降低。 - 把这道题目抽象来看，其实也是访问数组中特定的元素并进行覆盖操作，所以考虑双指针法。由于库函数
resize是衔接到原容器的尾部的来分配新的空间，所以考虑双指针从字符串尾部开始。如果resize是将新的空间接在原容器的头部，那么双指针就应该从头部开始。所以，这里的关键在于，resize出的空白的新空间在容器的哪个位置，双指针法就应该利用好新空间，避免不必要的元素位置交换等操作。 -
oldS从替换空格前的字符串尾部开始，newS从替换空格后（即resize后）的字符串尾部开始。- 若
oldS == ' '，则s[newS--] = '0'; s[newS--] = '2'; s[newS--] = '%'，然后oldS--去重写下一个字符。 - 若
oldS != ' '，s[newS--] = s[oldS--]，即直接重写当前oldS指向的字符。
- 若
- 如果按顺序从左到右遍历，并且新开一个字符串来保存替换空格后的字符串，虽然时间复杂度也是
初见题目时的代码
class Solution {
public:
string replaceSpace(string s) {
int count = 0;
for (auto& iter : s) {
if (iter == ' ') {
count++;
}
}
int oldS = s.size() - 1;
s.resize(s.size() + count * 2);
int newS = s.size() - 1;
while (oldS < newS) {
if (s[oldS] == ' ') {
s[newS--] = '0';
s[newS--] = '2';
s[newS--] = '%';
}
else {
s[newS--] = s[oldS];
}
oldS--;
}
return s;
}
};
LeetCode151 反转字符串中的单词
- 初见题目的想法：
- 首先要解决的问题是去除空格，
- 我对双指针法的掌握还不够熟悉，所以采用了分治的思想来解决前导空格和尾随空格。分别考虑去除前导空格和尾随空格的情况：
- 前导空格的处理：找到第一个单词开头作为
fast指针（oldS指针）的起始位置，字符串开头作为slow指针（newS指针）的起始位置。 - 尾随空格的处理：找到最后一个单词的最后一个字母的位置，作为
fast指针（oldS指针）的结束位置。 - 单词之间多余空格的处理：当
fast指针（oldS）遇到一个空格时，先将该空格赋值到slow（newS）的位置；然后若fast（oldS）再遇到一个空格，即连续遇到空格，则fast（oldS）直接跳过当前位置，直到fast（oldS）遇到非空格的字符。
- 前导空格的处理：找到第一个单词开头作为
- 我对双指针法的掌握还不够熟悉，所以采用了分治的思想来解决前导空格和尾随空格。分别考虑去除前导空格和尾随空格的情况：
- 去除空格后，如何反转单词呢？首先我注意到，如果将整个字符串反转，那么单词就在反转后对应的位置上，但是此时单词的字母顺序也被反转了；所以，再分别将每个单词反转回来即可。
- 首先要解决的问题是去除空格，
初见题目的题解代码，还可以写得更简洁，逻辑更清晰
class Solution {
public:
string reverseWords(string s) {
int newS = 0;
int oldS = 0;
for (int i = 0; i < s.size(); i++) {
if (s[i] != ' ') {
oldS = i;
break;
}
}
int end = s.size() - 1;
while (end) {
if (s[end] != ' ') {
break;
}
end--;
}
end++;
while (oldS < end) {
while (oldS > 0 && s[oldS] == ' ' && s[oldS - 1] == ' ') {
oldS++;
continue;
}
s[newS++] = s[oldS++];
}
s.resize(newS);
reverse(s.begin(), s.end());
int start = 0;
for (int i = 0; i <= s.size(); i++) {
if (s[i] == ' ' || i == s.size()) {
reverse(s.begin() + start, s.begin() + i);
start = i + 1;
}
}
return s;
}
};
-
看了讲解之后的题解代码
-
因为我初见时的题解代码逻辑不够明确，所以在这里再明确一遍快慢指针法（双指针法）的思路，以及结合题目来入题：
-
fast来从左到右来遍历整个字符串，slow在fast遍历的过程中来按我们定义的规则来重写字符串（这里我们定义的规则就是去掉“多余的”空格）。所以，快慢指针法，即双指针法的代码框架应该是这样的：
int slow = 0; for (int fast = 0; fast < s.size(); fast++) { if (/* 符合我们定义的规则 */) { s[slow++] = s[fast];// 保留这个元素 } else { /* 一些处理数组元素或下标的操作 */ continue; } }或者这样的
int slow = 0; for (int fast = 0; fast < s.size(); fast++) { if (/* 不符合我们定义的规则 */) { /* 一些处理数组元素或下标的操作 */ continue; } else { s[slow++] = s[fast];// 保留我们需要的元素 } }- “多余的”空格：即字符串的前导空格，尾随空格以及单词之间一个以上的空格。将这个规则用代码来描述，填入快慢指针法的框架中。注意，每个单词之间要保留一个空格，所以当然不能单纯的舍弃所有空格，我认为代码随想录的题解的一个精妙之处就在于：快慢指针不仅可以删除元素，还可以添加元素。即使我们单纯的先舍弃所有空格，我们也有机会把需要的空格添加回来，这有时候可以让代码逻辑更加简洁清晰。
int slow = 0; for (int fast = 0; fast < s.size(); fast++) { if (s[fast] != ' ') {// 非空格是肯定要保留的，直接跳过所有空格 if (slow != 0){// 需要空格的时候再加上，只有首个单词前面没有空格 s[slow++] = ' ';// 不是首个单词的话，我们手动给它前面加上一个空格 } while (fast < s.size() && s[fast] != ' ') {// 补全这个单词 s[slow++] = s[fast++]; } }- 先删除元素，在需要的情况下再添加回来。这道题加深了我对双指针法的理解，快指针遍历原来的数组，慢指针不断构造我们需要的数组。
-
-
完整的题解代码如下，我这里使用了STL的迭代器写法，注意C++的迭代器严格遵守左闭右开区间
class Solution {
public:
string reverseWords(string s) {
int slow = 0;
for (int fast = 0; fast < s.size(); fast++) {
if (s[fast] != ' ') {
if (slow != 0){
s[slow++] = ' ';
}
while (fast < s.size() && s[fast] != ' ') {
s[slow++] = s[fast++];
}
}
}
s.resize(slow);
reverse(s.begin(), s.end());
int start = 0;
for (int i = 0; i <= s.size(); i++) {
if (s[i] == ' ' || i == s.size()) {
reverse(s.begin() + start, s.begin() + i);// [begin, begin + i)
start = i + 1;// s[i] 是空格，所有下一个单词的开头应该再右移一位
}
}
return s;
}
};
LeetCode 剑指Offer58-II 左旋转字符串
- 初见题目时的想法：
- 双指针法，发现行不通，很容易陷入一直两两交换的误区
- 拆解字符串的反转：先反转整个字符串，然后分别反转
[begin, end - n)和[begin + s.size() - n, end)对应的子字符串
拆解字符串的旋转的题解，其实这也体现了一种分治的思想。（再次提醒，C++的STL迭代器遵循左闭右开）
class Solution {
public:
string reverseLeftWords(string s, int n) {
reverse(s.begin(), s.end());
reverse(s.begin(), s.end() - n);
reverse(s.begin() + s.size() - n, s.end());
return s;
}
};
以后解决问题时，我不要急于去模拟细节的过程，可以先整体来看，是否能用分治来把复杂的问题不断地分解成简单的问题。
