[数据结构与算法]代码随想录算法训练营第二天||977.有序数组的平方 ||209.长度最小的子数组||59.螺旋矩阵II

?977.有序数列的平方

题目链接：977. 有序数组的平方 - 力扣（LeetCode）

学习视频地址：双指针法经典题目 | LeetCode：977.有序数组的平方_哔哩哔哩_bilibili

看到此题的一个想法：因为数组是非降序排列，所以同时对两边元素的平方大小进行对比，所以我们要使用双指针法。

实现中遇到的困难：

因为笔者刚开始学习stl，对vector容器的使用并不熟练，所以在新数组的创建上出了一点问题。算法思想是明白的。

看完代码随想录的收获：对if循环条件有更深刻的认识，不要随便乱添加判断语句，有时会出现一些缺少判断的情况。促进了我对vector容器的学习。

源代码：

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
int k=nums.size()-1;
vector<int> Arr(nums.size(),0);
int i=0;
int j=nums.size()-1;
for(;i<=j;){
    if(nums[i]*nums[i]<nums[j]*nums[j]){
        Arr[k--]=nums[j]*nums[j];
        j--;
    }else{
        Arr[k--]=nums[i]*nums[i];
        i++;
    }
}
return Arr;
    }
};

209.长度最小的子数组

题目链接：209. 长度最小的子数组 - 力扣（LeetCode）

学习视频链接：拿下滑动窗口！ | LeetCode 209 长度最小的子数组_哔哩哔哩_bilibili

看到这个题的第一个想法：暴力解法。但是LeetCode直接显示超时了。

实现中遇到的困难：没有想到创造一个储存结果的变量。没有想去判断length和result的大小，直接输出length了出现了很大的问题。对c++语法不是很熟悉。

看完代码随想录的收获：学会了新的判断方式。学会了滑动窗口的本质。

源代码：

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
int result =INT32_MAX;//结果
int sum=0;//和
int length=0;//长度
int i=0;
for(int j=0;j<=nums.size()-1;j++){//j表示的是快指针
sum+=nums[j];
while(sum>=target){
length=j-i+1;
result=result>length?length:result;
sum-=nums[i++];
}
}
return result==INT32_MAX?0:result;
    }
};

59.螺旋矩阵

题目链接：59. 螺旋矩阵 II - 力扣（LeetCode）

视频链接：一入循环深似海 | LeetCode：59.螺旋矩阵II_哔哩哔哩_bilibili

看到题目的第一想法：想到了要控制边界，然后依次循环每一个边。

实现遇到的困难:想不出循环的次数，对边界没有设限。

看完代码随想录得到的收获：对模拟过程有了一个新的认识，对边界的把控有了新的理解

源代码：

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
    //用两个变量存放起始位置
int startx=0;
int starty=0;
    //一个存放最中间的坐标，一个存放边界值
int offset=1;
int mid=n/2;
int count=1;
vector<vector<int>>nums(n,vector<int>(n,0));
int i,j;
int loop=n/2;
while(loop--){//循环次数
i=startx;
j=starty;
for(;j<n-offset;j++){
    nums[i][j]=count++;
}
for(;i<n-offset;i++){
    nums[i][j]=count++;
}
for(j;j>starty;j--){
     nums[i][j]=count++;
}
for(i;i>startx;i--){
     nums[i][j]=count++;
}
offset++;
startx++;
starty++;
}
if(n%2){
    nums[mid][mid]=count;
}
return nums;
    }
};

对数组的总结：

常用方法：

1.二分法：

使用二分法的时候，要对循环的边界有明确的认定，要先确定是“左闭右闭”oder“左闭右开”等等，严格遵守循环不变量原则。

时间复杂度：O(logn)

2.双指针法：

可以在一个for循环下完成两个for循环得工作

时间复杂度：O(n)

3.滑动窗口：

能根据自序列的大小不断调整起始位置

时间复杂度：O(n)

4.模拟行为：

考察对“循环不变量”的遵守。

今日收获：学会了移动窗口，理解了模拟行为的实现。

学习时长：3小时左右，螺旋矩阵让我有点头疼。写博客也花了不少时间。