一进循环深似海

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

1.LeetCode 977.有序数组的平方

题目链接：https://leetcode.cn/problems/squares-of-a-sorted-array/

2.1自己看到题目的第一想法

思路：先进行平方，再进行排序

代码：

class Solution {
    public int[] sortedSquares(int[] nums) {
        //先解决每个元素平方之后
        //再解决平方后的新数组要按照顺序进行排序
        for(int i=0;i<nums.length;i++){
            nums[i]=nums[i]*nums[i];
        }
        //冒泡排序，就是用到两个指针啊
        for(int i=0;i<nums.length-1;i++){
            for(int j=i+1;j<nums.length;j++){
                if(nums[i]>nums[j]){
                    //因为要从小到大进行排序
                    //交换过程
                    int t=nums[i];
                    nums[i]=nums[j];
                    nums[j]=t;
                }//不是就不换
            }
        }
        return nums;
    }
}

2.2看完代码随想录之后

思路：

我们观察这个数组，不止有正数，还包含了负数，而且是从有序的
平方之后最大的，那么就是数组的左右两边最大，慢慢向内靠

左右两边最大，那我们用两个指针，一个是左边的，一个是右边的。左右两边慢慢向中间靠拢
左右两边的比较之后最大的一边就存储到新数组中，然后将该对应的指针向下移动

代码：

class Solution {
    public int[] sortedSquares(int[] nums) {
        //暴力解决完之后，我们尝试用其他算法
        //要平方（看能不能用库函数），要排序
        //双指针
        //我们观察这个数组，不止有正数，还包含了负数，而且是从有序的
        //平方之后最大的，那么就是数组的左右两边最大，慢慢向内靠
        //左右两边最大，那我们用两个指针，一个是左边的，一个是右边的。左右两边慢慢向中间靠拢
        //左右两边的比较之后最大的一边就存储到新数组中，然后将该对应的指针向下移动
        int[] arr=new int[nums.length];
        //新数组索引
        int k=arr.length-1;//我们准备最大元素的存到下标最大的，所以k赋值为arr.length-1
        int i=0;
        int j=nums.length-1;
        while(i<=j){
            //i>j的时候，证明已经遍历完数组中的元素了
            //i=j时，也需要加上，不然就会有一个元素漏加进新数组了
            if(nums[i]*nums[i]>nums[j]*nums[j]){
                arr[k]=nums[i]*nums[i];
                i++;
                k--;
            }else if(nums[i]*nums[i]<nums[j]*nums[j]){
                arr[k]=nums[j]*nums[j];
                j--;
                k--;
            }else if(nums[i]*nums[i]==nums[j]*nums[j]){
                arr[k]=nums[j]*nums[j];
                j--;
                k--;
            }
        }
        return arr;
}
}

2.LeetCode 209.长度最小的子数组

题目链接：https://leetcode.cn/problems/minimum-size-subarray-sum/

2.1自己看到题目的第一想法

思路1：自己想的也是用指针解决

代码：(报错)，遇到数据不断变化有需要保存进行比较的问题

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        //首先判断有没有跟target值一样的，有直接返回1
        for(int i=0;i<nums.length;i++){
            if(nums[i]==target){
                return 1;//因为数组长度是1
            }
        }
        //慢指针
        //没有与target值相等的，那就要遍历数组，每一个跟下一个进行相加看是否=target
        //如果<target，那就继续向后面一个加

        //快指针
        //如果>target,那就将快指针向后移动，重复慢指针操作
        //直到快指针全部遍历完，退出程序，返回0
        //int j=0;
        int result=0;
        //记录长度
        int len=0;
        for(int i=0;i<nums.length;i++){//如何保证数据是连续的//解决
            if(target>result){//这个可以解决最早找到符合加起来等于target数据，但不可以找到最小的数组
                result+=nums[i];
                len++;
            }else if(target==result){
                return len;
            }else if(target<result){
                i=i-len;
                len=0;
                result=0;
                //continue;
            }
        }
        return 0;
    }
}

2.2看完代码随想录之后

双指针思想:用一个for循环，里面的变量j为子数组的终止位置
另外一个指针为for之外的i变量，作为遍历下一个位置

代码：

//是找最小长度的数组，值大于等于s
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        //双指针思想
        //指针：用一个for循环，里面的变量j为子数组的终止位置
        //另外一个指针为for之外的i变量，作为遍历下一个位置
        int i=0;
        int sum=0;
        int oldlen;
        int result=Integer.MAX_VALUE;//初始化为java中的最大值
        for(int j=0;j<nums.length;j++){
            //因为是作为终止位置的指针，所以我们现在先在这里进行累加
            //累加到的值在和target作比较，如果大于等于target时，则记录当前子数组长度
            //并将初始位置向后移动一位
            sum+=nums[j];
            while(sum>=target){
                //记录长度
                oldlen=j-i+1;
                //进行更新最小的长度
                result=Math.min(result,oldlen);//在第一次时，最开始的初始值（也就是和最大值），与现在收集的长度进行比较，再赋值给result
                //在下一次，就是原始的长度跟先收集的长度进行比较

                //将现在的sum减掉初始位置的值，才能进行下一轮的添加
                sum=sum-nums[i];
                i++;
            }
        }
        return result==Integer.MAX_VALUE?0:result;
        //本来是直接返回result就行，但是我们要考虑到所有数组中元素加起来后依然是小于target的情况，就要返回0
    }
}

3.LeetCode ?59.螺旋矩阵II

题目链接：https://leetcode.cn/problems/spiral-matrix-ii/

3.1自己看到题目的第一想法

思路:懵圈圈

一进循环深似海，从此offer是路人

3.2自己实现过程中遇到哪些困难

1.不理解螺旋一圈（自己画图解决）

2.不明白圈数为n/2（画图理解）

3.当圈数为奇数，最后一个落下的不成圈的怎么办 arr[n/2][n/2]=n^2;

3.3看完代码随想录之后

代码：

class Solution {
    public int[][] generateMatrix(int n) {
        //一进循环深似海，从此offer是路人
        //一圈一圈解决
        //一圈中分为四条边分别取解决

        //第一圈：上行：左边第一个，到不包括右边最后一个
        //右行：右上角第一个，到不包括右下角的最后一个
        //下行：右下角第一个，到不包括左下角最后一个
        //上行：左下角第一个，到不包括左上角最后一个
        //二维数组，水平竖直两个坐标，startx,starty
        //int[x][y] int[i][j]
        int startx=0;
        int starty=0;
        int offset=1;
        //计数器
        int count=1;
        //判断循环次数
        int loop=0;

        int mid = n / 2;

        //为了不让i,j在每次的for中重置，我们把它定义到外面
        int i;
        int j;
        //用一个二维数组存数据
        int[][] arr=new int[n][n];

        //有多少圈顺时针的，我们就虚幻多少圈，到最后奇数圈我们就另外赋值
        while(loop++ < n / 2){
            //上行,startx是不变的，我们用starty.
        //因为左闭右开，最后一位在一行中是不遍历到的
        for(j=starty;j<n-offset;j++){
            arr[startx][j]=count++;
            //这样子startx就在变化
        }//此时j已经等于n-offset了，i还是0
        //startx是0，starty是n-offset

        //右行,starty是不变的，我们用startx
        for(i=startx;i<n-offset;i++){
            arr[i][j]=count++;
        }//此时j还是n-offset,i是n-offset.到最大值了
        //startx是0，starty是n-offset

        //下行
        //此时下标的横坐标不用变，纵坐标需要变
        for(;j>starty;j--){
            arr[i][j]=count++;
        }//此时j是0，i还是n-offset
        //startx是0，starty是n-offset

        //左行
        //此时下标的横坐标需要变化，纵坐标不需要变
        for(;i>startx;i--){
            arr[i][j]=count++;
        }//此时j为0，i为0
        //startx和starty同上

        //一圈结束完我们要
        startx++;
        starty++;
        offset+=1;//第二圈
        }

        //有多少圈顺时针的，我们就虚幻多少圈，到最后奇数圈我们就另外赋值
        if(n%2==1){
            arr[mid][mid]=count;
        }
        return arr;
    }
}

4.数组总结

文章链接：https://programmercarl.com/%E6%95%B0%E7%BB%84%E6%80%BB%E7%BB%93%E7%AF%87.html

1.数组基本概念

2.二分查找（区间确定边界）

3.双指针（解决移除元素，长度最小的子数组）

4.螺旋数组

5.今日收获

1.一进循环深似海，从此offer是路人,第一次接触螺旋矩阵，一开始还没有概念，画图帮助自己去理解。但还是写不出来，看了视频思路后，再尝试自己去写，就写出来了。

2.双指针真的好方便啊，高举双指针大旗。