您现在的位置是:首页 >技术杂谈 >代码随想录算法训练营15期 Day 2 | 977.有序数组的平方 、209.长度最小的子数组 、59.螺旋矩阵II 、总结网站首页技术杂谈
代码随想录算法训练营15期 Day 2 | 977.有序数组的平方 、209.长度最小的子数组 、59.螺旋矩阵II 、总结
简介代码随想录算法训练营15期 Day 2 | 977.有序数组的平方 、209.长度最小的子数组 、59.螺旋矩阵II 、总结
977.有序数组的平方
题目建议: 本题关键在于理解双指针思想
题目链接:力扣
思路一:暴力解算,直接将所有元素变成一个平方,然后进行排序。
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
for(int i = 0;i<nums.size();i++)
{
nums[i]=nums[i]*nums[i];
}
sort(nums.begin(),nums.end());
return nums;
}
};
思路二:双指针法,首先声明一个数组与原始的数组大小相同,然后由两头的指针由大到小进行排序。
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
//首先声明一个数组长度与原始的大小相同
vector<int> nums1(nums.size(),0);
//提供数组的长度,为以后使用提供便利
int k = nums.size()-1;
for(int i = 0,j=nums.size()-1;i<=j;)
{
if(nums[i]*nums[i]<nums[j]*nums[j])
{
nums1[k--]=nums[j]*nums[j];
j--;
}
else
{
nums1[k--]=nums[i]*nums[i];
i++;
}
}
return nums1;
}
};
209.长度最小的子数组
题目建议: 本题关键在于理解滑动窗口,这个滑动窗口看文字讲解 还挺难理解的,建议大家先看视频讲解。 拓展题目可以先不做。
题目链接:力扣
思路一:直接暴力计算,时间很长,不建议。
思路二:双指针法,使用两个指针将中间的数组提取出来。
双指针一般是使用一个for循环做了两个for循环的事情。
起始位置使用i表示,终止位置使用j表示。起始位置与终止位置之间的差距大于等于s,则进行改变。
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int result = INT32_MAX;//声明最大的长度
int i = 0;//起始位置
int sum = 0;//和
int length = INT32_MAX;//长度
for(int j = 0;j<nums.size();j++)//终止位置
{
sum+=nums[j];
while(sum>=target)//注意是while
{
length = j - i + 1;
sum = sum-nums[i];
i++;//起始位置向前移动
result = result < length ? result : length;
}
}
return result<INT32_MAX?result:0;
}
};
59.螺旋矩阵II
题目建议: 本题关键还是在转圈的逻辑,在二分搜索中提到的区间定义,在这里又用上了。
题目链接:力扣
关键在于四个边界的条件处理,一入循环深似海。注意循环不变量,坚持一个规则处理每一个边,按照左闭右开的规则。
由于一圈等于两行两列,因此,转动的是n/2圈。需要判断转动的圈数是奇数还是偶数。左闭右开,终止位置是不包含的。
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
//起始位置
int startx = 0;
int starty = 0;
//偏移量
int offset = 1;
//声明一个二维数组
vector<vector<int>> res(n, vector<int>(n, 0)); // 使用vector定义一个二维数组
//加入的数字
int count = 1;
//转动圈数
int circle = n/2;
while(circle--)//转动的圈数
{
int i,j;
for( j = starty;j<n-offset;j++)//第一行
{
res[startx][j]=count++;
}
for( i = startx;i<n-offset;i++)//右侧第一列
{
res[i][j]=count++;
}
for(;j>starty;j--)//下侧第一列
{
res[i][j]=count++;
}
for(;i>startx;i--)
{
res[i][j]=count++;
}
startx++;
starty++;
offset++;
}
if(n%2 == 1)
{
res[n/2][n/2]=n*n;
}
return res;
}
};
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。