算法（四）--双指针 && 滑动窗口 && 数组
双指针
当需要多次重复的遍历数组时，使用指向头尾的双指针并同时移动它们可以大大减少重复遍历的次数。
双指针的作用就在于可以跳过无用解。通过使用两个指针（通常一个指向数组的开始，另一个指向数组的末尾）并根据一定的条件同时移动这两个指针，可以有效地在遍历数组时减少不必要的重复遍历，从而提高算法的效率。此外，双指针技术还可以帮助跳过那些不满足特定条件的无用解，进一步优化搜索或计算过程。
两数之和II-输入是有序数组
注意输入的数组必须是非递减数组，如果不是，需要先排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
// 双指针的本质：缩减搜索空间，当你在使用双指针时，要持有这样一个思想，去尽可能的减少搜索空间。
// 如果当前指针下，另一个指针遍历的所有情况都不成立，就可以移动当前指针，以减少遍历次数
vector<int> twoSum(vector<int>& numbers, int target) {
// 本思想：把number数组变成一个二维搜索空间，长和宽都是numbers，注意j要大于等于i，因为不能出现重复。
// j从后往前遍历，i从前遍历；
// 当num[j] + num[i] < target，说明再往后遍历j就没必要了，往前移动i指针
// 当num[j] + num[i] > target, 说明再往前遍历i就没必要了，往后移动j指针
int i = 0;
int j = numbers.size() - 1;
while(true) {
if(numbers[i] + numbers[j] == target) break;
if(numbers[i] + numbers[j] < target) {
i++;
continue;
}
if(numbers[i] + numbers[j] > target) {
j--;
continue;
}
}
return {i + 1, j + 1};
}
};
数组
反转数组
先对k取余n；然后将整个数组反转，在反转0到k-1（前k个），再反转k到n-1（剩下的）。
1
2
3
4
5
6
7
8
9
10
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
k %= n;
reverse(nums.begin(), nums.end());
reverse(nums.begin(), nums.begin() + k);
reverse(nums.begin() + k, nums.end());
}
};
数组移除
数组移除元素的本质就是覆盖！对数组内容进行更新，以达到移除某个元素的效果。常用的是双指针法，通过快慢指针，慢指针指向第一位需要更新的数组，也就是慢指针之前的位置已处理完成；快指针寻找新数组元素
移除零
维护快慢指针，慢指针表示已经处理完成的数组的后一位，快指针表示当前位置。当当前位置不为0时，将当前位置的值赋值给已处理完成的数组的后一位，然后两个指针都向后移动一位。
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int i = 0;
for(int j = 0; j < nums.size(); j++) {
if(nums[j] != val) {
nums[i] = nums[j];
i++;
}
}
return i;
}
};
移除元素
移动0的翻版，就把指定元素移动然后删除处理完指针到队尾的剩余部分。
删除有序数组中的重复项
维护快慢指针，慢指针表示已经无重复有序的数组的后一位，快指针表示当前位置，当快指针不同于前一位时(fast[i] != fast[i-1])，将慢指针赋值为快指针，并且移动一位。注意初始化slow和fast为1。
删除有序数组中的超过k个的重复项
维护快慢指针，慢指针表示已经无重复有序的数组的后一位，快指针表示当前位置，当快指针不同于前k位时(fast[i] != fast[i-k])，将慢指针赋值为快指针，并且移动一位。注意初始化slow和fast为k。
轮转数组
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。有个直接的技巧，先反转整个数组，然后反转前k个，再反转后n-k个。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
void reverse(vector<int>& nums, int start, int end) {
while (start < end) {
swap(nums[start], nums[end]);
start++;
end--;
}
}
void rotate(vector<int>& nums, int k) {
k %= nums.size();
reverse(nums,0,nums.size()-1);
reverse(nums,0,k-1);
reverse(nums,k,nums.size()-1);
}
};
罗马数字转整数
如果出现小的数字出现在大的数字的左边，直接取反。
整数转罗马数字
将十三个罗马数字从大到小列出，将target一致减去当前最大数，知道不能减去就换较小的数接着减。每减去一个数，就往答案里添加对应的罗马数字。
最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ““。
思路：先排序所有字符，然后比较第一个和最后一个字符的公共前缀。
1
2
3
4
5
6
7
8
string longestCommonPrefix(vector<string>& strs) {
sort(strs.begin(), strs.end());
string f = strs.front(), b = strs.back();
int i = 0;
int n = min(f.size(), b.size());
for(i; i < n && f[i] == b[i]; i++);
return i == 0 ? "" : f.substr(0,i);
}
反转字符串中的单词
维护一个idx指针指向已经处理完成的字符串的后一位，先将整个字符串反转，找到第一个不为空的字符的位置。先将当前idx指针加空格隔开新单词，idx++，然后在找下一个为空的字符的位置的过程中，将当前字符付给idx指向的字符位置；最后反转当前单词。然后将start重置为end。直到start到字符串末尾结束。最后将idx到end()的字符删除掉。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
string reverseWords(string s) {
// reverse 是左闭右开区间，不包含右边的迭代器
reverse(s.begin(), s.end());
int idx = 0;
for(int start = 0; start < s.size(); start++) {
if(s[start]!=' ') {
if(idx!=0) s[idx++] = ' ';
// find cur word's end and renew idx
int end = start;
while(end < s.size()&&s[end]!=' ') s[idx++] = s[end++];
reverse(s.begin()+idx-(end-start), s.begin()+idx);
start = end;
}
}
// delete idx 之后的字符
s.erase(s.begin()+idx, s.end());
return s;
}
或者用字符流来分割字符，字符流是按空格分割字符的神器啊！！！
1
2
3
4
5
6
7
8
9
10
11
12
13
// 用字符流来分割字符！！！
string reverseWords(string s) {
reverse(s.begin(), s.end());
stringstream ss(s);
string cur, ans;
while(ss>>cur) {
reverse(cur.begin(), cur.end());
cur += ' ';
ans += cur;
}
ans.erase(ans.size()-1, 1);
return ans;
}
Z字形变换
z字形变换的本质就是标记字符串然后根据标记的结果去重新排序即可。标记规则是，1-numRows-1-numRows-…，假设numPows的大小为4，那就是123432123432…
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
string convert(string s, int numRows) {
if(numRows==1)return s;
string ans {""};
vector<int> res = registers(s.size(), numRows);
for(int i = 1; i <= numRows; i++) {
for(int pos = 0; pos < res.size(); pos++) {
if(res[pos] == i) ans += s[pos];
}
}
return ans;
}
vector<int> registers(int len, int numRows) {
vector<int> r;
vector<int> res;
for(int i = 1; i < numRows; i++) r.emplace_back(i);
for(int i = numRows; i > 1; i--) r.emplace_back(i);
for(int i = 0; i < len; i++) {
res.emplace_back(r[i%r.size()]);
}
return res;
}
找出字符串中第一个匹配项的下标
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。
1
2
3
4
5
6
7
8
9
10
11
12
13
//扫描一遍O n
int strStr(string haystack, string needle) {
int cur = 0;
for(int search = 0; search < haystack.size(); search++) {
if(haystack[search] == needle[cur]) {
int find = search;
while(find < haystack.size() && cur < needle.size() && haystack[find] == needle[cur]){find++;cur++;}
if(cur == needle.size()) return search;
cur = 0;
}
}
return -1;
}
滑动窗口
滑动窗口的本质就是不断移动左边界和右边界，最终实现我们想要的结果。通常用一个for循环来遍历右边界，也就是滑动窗口的终止位置（如果是左边界，那么存在溢出问题）; 确定如何移动左边界是滑动窗口的关键，通常使用一个while循环来动态确定左边界 解题模式为
1
2
3
4
5
6
7
for(int i = 0; i < n; i++) {
while(j < n) {
// 滑动窗口的逻辑
j++;
}
// 滑动窗口的逻辑
}
根据i的左右位置，分为左滑动窗口和右滑动窗口