您现在的位置是:首页 >其他 >代码随想录算法训练营第二天|双指针、滑动窗口、模拟网站首页其他
代码随想录算法训练营第二天|双指针、滑动窗口、模拟
简介代码随想录算法训练营第二天|双指针、滑动窗口、模拟
力扣977.有序数组的平方
给你一个按非递减顺序排序的整数数组 nums,返回每个数字的平方组成的新数组,要求也按非递减顺序排序。
示例:
输入:nums = [-4,-1,0,3,10]
输出:[0,1,9,16,100]
解释:平方后,数组变为 [16,1,0,9,100]
排序后,数组变为 [0,1,9,16,100]
思路分析:排序算法的最优复杂度是O(nlogn),而这个题目要求的时间复杂度为O(n),需要非递减顺序这一条件得出原数组的绝对值是先减后增的
自己写的:
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int minv = 1e8, mid;
//找到绝对值最小的下标,即分界点
for(int i = 0; i < nums.size(); i ++ ){
nums[i] *= nums[i];
if(nums[i] < minv){
minv = nums[i];
mid = i;
}
}
//从分界点往两边走,进行比较,把最小的数放入res数组
int i = mid - 1, j = mid;
vector<int> res;
for(; i >= 0 && j < nums.size(); ){
if(nums[i] > nums[j]){
res.push_back(nums[j]);
j ++;
}
else{
res.push_back(nums[i]);
i --;
}
}
if(i >= 0)
while(i >= 0){
res.push_back(nums[i]);
i --;
}
if(j < nums.size())
while(j < nums.size()){
res.push_back(nums[j]);
j ++;
}
return res;
}
};
代码随想录:
class Solution {
public:
vector<int> sortedSquares(vector<int>& A) {
int k = A.size() - 1;
vector<int> result(A.size(), 0);
//直接从左右端点开始比较
for (int i = 0, j = A.size() - 1; i <= j;) { // 注意这里要i <= j,因为最后要处理两个元素
if (A[i] * A[i] < A[j] * A[j]) {
result[k--] = A[j] * A[j];
j--;
}
else {
result[k--] = A[i] * A[i];
i++;
}
}
return result;
}
};
滑动窗口
题目
力扣209.长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数
target
。
找出该数组中满足其和≥ target
的长度最小的 连续子数组[numsl, numsl+1, ..., numsr-1, numsr]
,并返回其长度。如果不存在符合条件的子数组,返回0
。
示例:
输入:target = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组
思路分析:
1.答案区间的右端点一定在区间[0, nums.size()]内
2.先找到最小的j使得区间[0, j]内元素的和 ≥ target
3.对于之后的每一个j,找到最大的i使得区间[i, j]内的元素之和 ≥ target
4.记录这些区间的最小长度,即为答案
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int i = 0, j = 0;
int sum = 0; //区间[i, j]中元素的和
int minv = 1e5;
//2.找到最小的j使得区间[0, j]内的元素之和 ≥ target
while(j < nums.size() && sum < target) sum += nums[j ++];
if(j >= nums.size() && sum < target) return 0;
minv = min(minv, j);
//因为前面只是求了[0, j]区间,但可能存在i使得[i, j]区间也满足
//所以j需要回退一个参加下面的循环运算
j --;
for(; j < nums.size(); j ++ ){
//3.对于每个j,找到最大的i使得区间[i, j]内的元素之和 ≥ target
while(i < j && sum - nums[i] >= target){
sum -= nums[i];
i ++;
}
//4.记录最小长度
minv = min(minv, j - i + 1);
//j前进一个单位,更新sum
if(j < nums.size() - 1) sum += nums[j + 1];
}
return minv;
}
};
模拟
题目
力扣59.螺旋矩阵 II
给你一个正整数
n
,生成一个包含1
到n2
所有元素,且元素按顺时针顺序螺旋排列的n x n
正方形矩阵matrix
。
示例:
输入:n = 3
输出:[ [1,2,3],[8,9,4],[7,6,5] ]
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> res(n, vector<int>(n)); // 分配内存空间
vector<vector<int>> flag(n, vector<int>(n)); // 分配内存空间
//控制方向(右、下、左、上)
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
//d是前进方向,0为右,1为下,2为左,3为上
int d = 0;
pair<int, int> pos = {0, 0};
for(int i = 1; i <= n * n; i++ ){
res[pos.first][pos.second] = i;
//走过的地方标记为1,不能再走
flag[pos.first][pos.second] = 1;
int x1 = pos.first + dx[d], y1 = pos.second + dy[d];
//检查继续往此方向走是否合法
if((x1 < 0 || x1 == n || y1 < 0 || y1 == n) || flag[x1][y1]) d = (d + 1) % 4;
//更新坐标
pos = {pos.first + dx[d], pos.second + dy[d]};
}
return res;
}
};
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。