算法训练营day02-有序数组的平方 +长度最小的子数组+螺旋矩阵II

一、977.有序数组的平方

题目链接：https://leetcode.cn/problems/squares-of-a-sorted-array/
文章讲解：https://programmercarl.com/0977.%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E7%9A%84%E5%B9%B3%E6%96%B9.html
视频讲解： https://www.bilibili.com/video/BV1QB4y1D7ep

1.1 初见思路

双指针，左指针跟右指针的数字进行平方后的比较，最终结果从右往左开始赋值

1.2 具体实现

class Solution {
    public int[] sortedSquares(int[] nums) {
        int left=0;
        int right=nums.length-1;
        int[] res = new int[nums.length];
        int index=nums.length-1;
        while(left<=right){
            if(nums[left]*nums[left] > nums[right]*nums[right]){
                res[index]=nums[left]*nums[left];
                left++;
                index--;
            }
            else{
                res[index]=nums[right]*nums[right];
                right--;
                index--;
            }
        }
        return res;
    }
}

1.3 重难点

• 双指针的while循环条件是<=

二、 209.长度最小的子数组

题目链接：https://leetcode.cn/problems/minimum-size-subarray-sum/
文章讲解：https://programmercarl.com/0209.%E9%95%BF%E5%BA%A6%E6%9C%80%E5%B0%8F%E7%9A%84%E5%AD%90%E6%95%B0%E7%BB%84.html
视频讲解：https://www.bilibili.com/video/BV1tZ4y1q7XE

2.1 初见思路

双指针，更形象的来说是滑动窗口。
从第一位开始，首先找到满足总和条件的数组。每右指针移动一位，然后就将左指针一直移动到窗口内的总和满足条件同时窗口个数最小。

2.2 具体实现

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        //从第一位开始，首先找到满足总和条件的数组。每右指针移动一位，然后就将左指针一直移动到窗口内的总和满足条件同时窗口个数最小。
        int left=0;
        int sum=0;
        int res=Integer.MAX_VALUE;
        for(int right=0;right<nums.length;right++){
            sum+=nums[right];
            while(sum>=target){
                
                res=Math.min(res,right-left+1);
                sum-=nums[left++];
            }
        }
        return res==Integer.MAX_VALUE?0:res;
    }
}

2.3 重难点

• 滑动窗口的实现方式

三、 59.螺旋矩阵II

题目链接：https://leetcode.cn/problems/spiral-matrix-ii/
文章讲解：https://programmercarl.com/0059.%E8%9E%BA%E6%97%8B%E7%9F%A9%E9%98%B5II.html
视频讲解：https://www.bilibili.com/video/BV1SL4y1N7mV/

3.1 初见思路
十一点半还在现场加班，头很晕 ，没太多思路，直接干视频了！

3.1.1 看题解后
左闭右开！记住！！

3.2 具体实现

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] nums = new int[n][n];
        int startX = 0, startY = 0;  // 每一圈的起始点
        int offset = 1;
        int count = 1;  // 矩阵中需要填写的数字
        int loop = 1; // 记录当前的圈数
        int i, j; // j 代表列, i 代表行;

        while (loop <= n / 2) {

            // 顶部
            // 左闭右开，所以判断循环结束时， j 不能等于 n - offset
            for (j = startY; j < n - offset; j++) {
                nums[startX][j] = count++;
            }

            // 右列
            // 左闭右开，所以判断循环结束时， i 不能等于 n - offset
            for (i = startX; i < n - offset; i++) {
                nums[i][j] = count++;
            }

            // 底部
            // 左闭右开，所以判断循环结束时， j != startY
            for (; j > startY; j--) {
                nums[i][j] = count++;
            }

            // 左列
            // 左闭右开，所以判断循环结束时， i != startX
            for (; i > startX; i--) {
                nums[i][j] = count++;
            }
            startX++;
            startY++;
            offset++;
            loop++;
        }
        if (n % 2 == 1) { // n 为奇数时，单独处理矩阵中心的值
            nums[startX][startY] = count;
        }
        return nums;
    }
}

3.3 重难点

• 左闭右开
• 循环次数计算