【代码随想录算法训练Day2】LeetCode 977.有序数组的平方、LeetCode 209.长度最小的子数组、LeetCode 59.螺旋矩阵II

Day2 数组、双指针

LeetCode 977.有序数组的平方【排序/双指针】

要将数组的每个元素平方后在按非递减的顺序，最简单的方法就是先将每个数平方，再将结果数组排序。

解法1：排序

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        vector<int> ans;
        for(int i=0;i<nums.size();i++)  ans.push_back(nums[i]*nums[i]);
        sort(ans.begin(),ans.end());
        return ans;
    }
};

这里有一个小小的问题，vector在初始化之前不能用下标访问，否则会报错，也就是如果写成ans[i]=nums[i]*nums[i]是会报错的：runtime error: reference binding to null pointer of type ‘int’。

解法2：双指针算法

双指针算法的想法是基于本题的条件，原数组本来就是按照非递减的顺序排好的，我们可以利用这一条件，这种情况下，数组两端的数的平方一定比它内侧的数的平方要大，所以我们利用这一点，用两个指针分别从原数组两端选择最大的数，将它的平方逆序排到结果数组中即可。

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

LeetCode 209.长度最小的子数组【滑动窗口】

第一想法当然是暴力算法，但时间复杂度是n²，太大了，这里就不考虑了，除非万不得已，否则还是动动脑子吧。

解法：滑动窗口

滑动窗口就是实现了用一遍循环解决了两遍循环的问题，我们不必再用两遍循环处理子数组的两端，而是利用题目的条件，只在循环中处理右边界，左边界在特殊情况下专门处理，这样就能省下很多时间。

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int i=0,sum=0,len=0,res=INT32_MAX;
        for(int j=0;j<nums.size();j++){
            sum+=nums[j];
            while(sum>=target){//部分和大于target时要用while不断右移左边界，保证窗口宽度最小
                len=(j-i+1);
                res=res<len?res:len;
                sum-=nums[i++];
            }
        }
        return res==INT32_MAX?0:res;
    }
};

LeetCode 59.螺旋矩阵II【模拟】

看似简单的转圈圈，要处理的边界条件却不少，处理每一条边的时候该处理几个元素，如何保证不重复、不遗漏，都是很关键的问题。一杯茶一包烟，螺旋矩阵转一天。

解法1：直接模拟

如果你对自己的边界处理很有自信，那就像贪吃蛇一样出发就可以了，一直向前，然后自己的数字变大，直到碰到已经处理过的元素或者边界为止，然后转弯继续走，按右→下→左→上的顺序循环往复，直到数字走到n*n为止。

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> ans(n,vector<int>(n,0));
        int i=0,j=0,x=2;
        ans[0][0]=1;
        while(x<=n*n){
            while(j<n-1 && ans[i][j+1]==0) ans[i][++j]=x++;//右
            while(i<n-1 && ans[i+1][j]==0) ans[++i][j]=x++;//下
            while(j>0 && ans[i][j-1]==0) ans[i][--j]=x++;//左
            while(i>0 && ans[i-1][j]==0) ans[--i][j]=x++;//上
        }
        return ans;
    }
};

解法2：详细模拟

如果直接模拟有一定困难，那么我们可以对每次转圈，走过的每一条边都进行一下详细的分析，先确定圈数，然后对每次循环都保证走过的每条边都是在合理范围内的，如果边长为奇数，那么特判中心元素即可，比较复杂，但很详细，容易理解。

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> ans(n,vector<int>(n,0));
        int startx=0,starty=0;//每圈循环的起始位置
        int loop=n/2;//循环的圈数
        int mid=n/2;//矩阵中间位置，用于在n为奇数时为最中间的格赋值
        int cnt=1;//控制赋值的大小
        int offset=1;//控制每一条边的长度
        int i,j;
        while(loop--){
            i=startx,j=starty;

            while(j<n-offset) ans[i][j++]=cnt++;
            while(i<n-offset) ans[i++][j]=cnt++;
            while(j>starty) ans[i][j--]=cnt++;
            while(i>startx) ans[i--][j]=cnt++;
            startx++;
            starty++;
            offset++;
        }
        if(n%2) ans[mid][mid]=cnt;
        return ans;
    }
};