双指针算法(其它类型)
leetcode.977
- 链接https://leetcode.cn/problems/...
- 解题方法:有序数组的平方最大值一定在数组的两侧
i指针从前向后遍历,j指针从后向前遍历,k指针用来存储新数组放置在数组前后均可(本题题解放在数组末尾)
将nums[i]的平方与nums[j]的平方作比较,k指针将较大的数存到答案数组当中,同时移动较大的数的指针和k的指针
如果将k指针放在数组首位则将k指针将较小的数存到答案数组当中,同时移动较小的数的指针和k的指针 leetcode解题代码
class Solution { public: vector<int> sortedSquares(vector<int>& nums) { int n = nums.size(); vector<int>res(n); for (int i = 0, j = n - 1, k = n - 1; i <= j;){ if (nums[i] * nums[i] > nums[j] * nums[j]){ res[k] = nums[i] * nums[i]; i ++, k --; } else{ res[k] = nums[j] * nums[j]; j --, k --; } } return res; } };
- ACM模式调试
输入
第一行输入n表示数组长度
第二行输入表示原数组
-4 -1 0 3 10
输出
0 1 9 16 100
调试代码
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> nums(n);
for (int i = 0; i < n; i ++) cin >> nums[i];
vector<int> res(n);
for (int i = 0, j = n - 1, k = n - 1; i <= j;){
if (nums[i] * nums[i] > nums[j] * nums[j]){
res[k] = nums[i] * nums[i];
i ++, k --;
}
else{
res[k] = nums[j] * nums[j];
j --, k --;
}
}
for (auto c: res){
cout << c << ' ';
}
return 0;
}
滑动窗口算法
leetcode.209
- 链接https://leetcode.cn/problems/...
- 解题方法:由于均为正整数,如果找到一段[j, i]满足条件的最小段,当i向右移动时,j同时要向右移动
将i,j指针同时放在数组首位,i指针向后移动并用sum记录nums[i]的总和
当sum-nums[j]>=target
时说明j指针可以跟随i向右移动
当满足sum>=target
时,用res记录[j, i]长度 leetcode解题代码
class Solution { public: int minSubArrayLen(int target, vector<int>& nums) { int sum = 0, res = INT_MAX; for (int i = 0, j = 0; i < nums.size(); i ++){ sum += nums[i]; while (sum - nums[j] >= target){ sum -= nums[j]; j ++; } if (sum >= target) res = min(res, i - j + 1); } if (res == INT_MAX) return 0; return res; } };
- ACM模式调试
输入
第一行输入n表示数组长度,target表示目标值
第二行输入表示原数组
6 7
2 3 1 2 4 3
输出
2
调试代码
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main()
{
int n, target;
cin >> n >> target;
vector<int> nums(n);
for (int i = 0; i < n; i ++) cin >> nums[i];
int sum = 0, res = INT_MAX;
for (int i = 0, j = 0; i < n; i ++){
sum += nums[i];
while (sum - nums[j] >= target){
sum -= nums[j];
j ++;
}
if (sum >= target) res = min(res, i - j + 1);
}
if (res == INT_MAX) cout << 0 << endl;
else cout << res << endl;
return 0;
}
leetcode.3
- 链接https://leetcode.cn/problems/...
- 解题方法:与上题类似,需要用一个哈希表存储[j, i]段中字符
leetcode解题代码
class Solution { public: int lengthOfLongestSubstring(string s) { int res = 0; unordered_map<char, int> cnt; for (int i = 0, j = 0; i < s.size(); i ++){ cnt[s[i]] ++; while (cnt[s[i]] > 1){ cnt[s[j]] --; j ++; } res = max(res, i - j + 1); } return res; } };
- ACM模式调试
输入
第一行输入表示字符串s
abcabcbb
输出
3
调试代码
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
int main()
{
string s;
getline(cin, s);
int res = 0;
unordered_map<char, int> cnt;
for (int i = 0, j = 0; i < s.size(); i ++){
cnt[s[i]] ++;
while (cnt[s[i]] > 1){
cnt[s[j]] --;
j ++;
}
res = max(res, i - j + 1);
}
cout << res << endl;
return 0;
}
leetcode.904
- 链接https://leetcode.cn/problems/...
- 解题方法:本题题意与上题类似,需要用一个哈希表存储[j, i]段中字符出现的次数,同时还要记录水果的种类,题目要求水果种类不超过2
leetcode解题代码
class Solution { public: int totalFruit(vector<int>& fruits) { int res = 0, type = 0;// res记录答案,type表示水果的种类 unordered_map<int, int> cnt;// cnt记录字符出现的次数 for (int i = 0, j = 0; i < fruits.size(); i ++){ cnt[fruits[i]] ++; if (cnt[fruits[i]] == 1) type ++;// 如果字符第一次出现说明是一种水果 while (type > 2){ cnt[fruits[j]] --; if (cnt[fruits[j]] == 0) type --; j ++; } res = max(res, i - j + 1); } return res; } };
- ACM模式调试
输入
第一行n表示fruits数组长度
第二行表示fruits数组
3
1 2 2
输出
3
调试代码
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> fruits(n);
for (int i = 0; i < n; i ++) cin >> fruits[i];
int res = 0, type = 0;
unordered_map<int, int> cnt;
for (int i = 0, j = 0; i < n; i ++){
cnt[fruits[i]] ++;
if (cnt[fruits[i]] == 1) type ++;
while (type > 2){
cnt[fruits[j]] --;
if (cnt[fruits[j]] == 0) type --;
j ++;
}
res = max(res, i - j + 1);
}
cout << res << endl;
return 0;
}
leetcode.76
- 链接https://leetcode.cn/problems/...
- 解题方法:本题题意与上题类似,需要用两个哈希表分别存储两个字符串
最后输出结果的时候需要特判 leetcode解题代码
class Solution { public: string minWindow(string s, string t) { string res; int cnt = 0;// 有效字符的数量 unordered_map<char, int> hs, ht; for (auto c: t) ht[c] ++; for (int i = 0, j = 0; i < s.size(); i ++){ hs[s[i]] ++; if (hs[s[i]] <= ht[s[i]]) cnt ++;// 是一个有效字符 while (hs[s[j]] > ht[s[j]]){ hs[s[j]] --; j ++; } if (cnt == t.size()){ if (res.empty() || i - j + 1 < res.size()) res = s.substr(j, i - j + 1); } } return res; } };
- ACM模式调试 与leetcode.3类似
螺旋矩阵
leetcode.54
- 链接https://leetcode.cn/problems/...
- 解题方法:
从左上角出发,按照顺时针顺序分别是向右向下向左向上,如果初始坐标为(0,0)
向右(0,1)向下(1,0)向左(0,-1)向上(-1,0)
所以x有四个取值{0, 1, 0, -1},y有四个取值{1, 0, -1, 0}
按照每一个方向一直走,走到不能走为止
不能走有两种可能:1.出界 2.走到已经走过的位置 leetcode解题代码
class Solution { public: vector<int> spiralOrder(vector<vector<int>>& matrix) { vector<int> res; int n = matrix.size(); int m = matrix[0].size(); vector<vector<bool>> st(n, vector<bool>(m)); int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; for (int i = 0, x = 0, y = 0, d = 0; i < n * m; i ++){ res.push_back(matrix[x][y]); st[x][y] = true; int a = x + dx[d], b = y + dy[d]; if (a < 0 || a >= n || b < 0 || b >= m || st[a][b]){ d = (d + 1) % 4; a = x + dx[d], b = y + dy[d]; } x = a, y = b; } return res; } };
- ACM模式调试
输入
第一行表示n行m列向量
后面n行m列表示向量的值
3 3
1 2 3
4 5 6
7 8 9
输出
1 2 3 6 9 8 7 4 5
调试代码
#include <iostream>
#include <vector>
using namespace std;
int main(){
int n, m;
cin >> n >> m;
int metrix[n][m];
for (int i = 0; i < n; i ++){
for (int j = 0; j < m; j ++){
cin >> metrix[i][j];
}
}
vector<vector<bool>> st(n, vector<bool>(m));
vector<int> res;
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
for (int i = 0, x = 0, y = 0, d = 0; i < n*m; i ++){
res.push_back(metrix[x][y]);
st[x][y] = true;
int a = x + dx[d], b = y + dy[d];
if (a < 0 || a >= n || b < 0 || b >= m || st[a][b]){
d = (d + 1) % 4;
a = x + dx[d], b = y + dy[d];
}
x = a, y = b;
}
for (auto c: res){
cout << c << ' ';
}
return 0;
}
leetcode.59
- 链接https://leetcode.cn/problems/...
- 解题方法:与上一题类似
leetcode解题代码
class Solution { public: vector<vector<int>> generateMatrix(int n) { vector<vector<int>> res(n, vector<int>(n)); int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; for (int i = 1, x = 0, y = 0, d = 0; i <= n * n; i ++){ res[x][y] = i; int a = x + dx[d], b = y + dy[d]; if (a < 0 || a >= n || b < 0 || b >= n || res[a][b]){ d = (d + 1) % 4; a = x + dx[d], b = y + dy[d]; } x = a, y = b; } return res; } };
- ACM模式调试 与上一题类似
解题参考:https://www.acwing.com/
刷题顺序:https://www.programmercarl.com/