代码随想录算法训练营第2天 | 数组滑动窗口、螺旋打印

有序数组的平方。常规方法复习冒泡排序，也可以使用双指针。因为有序数组的平方，最大值一定在两侧，最小值在中间。可以两侧往中间收拢。

2024年7月4日笔记：双指针法，两侧往中间逼近一定是从大到小，然后给res数组倒着填即可实现从小到大。

题977. 有序数组的平方

class Solution {
    public int[] sortedSquares(int[] nums) {
        int len = nums.length;
        int[] res = new int[len];
        int l=0,r=len-1;
        int cnt=len-1;
        while(l<=r){
            //看l大还是r大，谁大就先填谁然后向内移动一格
            if(abs(nums[l])>abs(nums[r])){
                res[cnt] = nums[l]*nums[l];
                cnt-=1;
                l+=1;
            }else{
                res[cnt] = nums[r]*nums[r];
                cnt-=1;
                r-=1;
            }
        }
        return res;
    }

    public int abs(int x){
        if(x<0){
            return -x;
        }else{
            return x;
        }
    }
}

长度最小的子数组，重点复习滑动窗口。
始终维护sum等于l和r之间所有值的和，然后不断和target比较，如果大了l就进，如果小了r就进，每次记录长度，最后就可以获得满足要求的最小长度。

题209. 长度最小的子数组

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int minLen=nums.length+1;
        int l=0,r=0;//左闭右闭
        int sum=nums[0];
        while(r<nums.length){
            if(sum>=target){
                if(minLen>r-l+1){
                    minLen = r-l+1;
                }
                l+=1;
                sum-=nums[l-1];
            }else{
                r+=1;
                if(r<nums.length){
                    sum+=nums[r];
                }
            }
        }
        if(minLen==nums.length+1){
            return 0;
        }
        return minLen; 
    }
}

螺旋矩阵
单独定义好边界，每轮过后更新边界，然后使用方向标记来记录当前的行进方向。

注意：

• x和y对应的行和列不要混淆；
• 上边界初始化时即可设置为1，其他边界初始化为0。

题59. 螺旋矩阵 II

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] res = new int[n][n];
        int cur = 1;//右下左上分别用1234代表，一开始是右侧
        int x=0,y=0;//右正下正
        int a1=n-1,a2=n-1,a3=0,a4=1;//代表初始边界
        for(int i=1;i<=n*n;i++){
            res[x][y]=i;
            //如果当前是右侧，那么下一步只能右或者下
            //右侧和下侧边界都是最多n-1
            if(cur==1){
                if(y+1>a1){
                    cur=2;
                    x+=1;
                    //更新右侧边界
                    a1-=1;
                }else{
                    y+=1;
                }
            }else if(cur==2){
                if(x+1>a2){
                    cur=3;
                    y-=1;
                    //更新下侧边界
                    a2-=1;
                }else{
                    x+=1;
                }
            }else if(cur==3){
                if(y-1<a3){
                    cur=4;
                    x-=1;
                    //更新左侧边界
                    a3+=1;
                }else{
                    y-=1;
                }
            }else{
                if(x-1<a4){
                    cur=1;
                    y+=1;
                    //更新上侧边界
                    a4+=1;
                }else{
                    x-=1;
                }
            }
        }
        return res;
    }
}

题54. 螺旋矩阵

class Solution {
    public static List<Integer> spiralOrder(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        List<Integer> list1 = new ArrayList<>();
        int cur = 1;
        int a1=n-1,a2=m-1,a3=0,a4=1;//右下左上的起始边界
        int x=0,y=0;
        for(int i=0;i<m*n;i++){
            list1.add(matrix[x][y]);
            if(cur==1){
                if(y+1>a1){
                    cur=2;
                    x+=1;
                    a1-=1;
                }else{
                    y+=1;
                }
            }else if(cur==2){
                if(x+1>a2){
                    a2-=1;
                    cur=3;
                    y-=1;
                }else{
                    x+=1;
                }
            }else if(cur==3){
                if(y-1<a3){
                    a3+=1;
                    cur=4;
                    x-=1;
                }else{
                    y-=1;
                }
            }else{
                if(x-1<a4){
                    a4+=1;
                    cur=1;
                    y+=1;
                }else{
                    x-=1;
                }
            }
        }
        return list1;
    }
}