Leetcode刷题day2|数组二|977.有序数组的平方，209.长度最小的子数组，59.螺旋矩阵II

古城微笑少年丶 2024-04-01 19:47 18阅读 0赞

##  ##

#### 文章目录 ####

*  
 *   *  一、有序数组的平方
     *   *  错误的尝试
         *  思路
         *  注意
         *  AC代码
         *  暴力版本
         *  双指针方法
     *  二、长度最小的子数组
     *   *  错误的尝试
         *  思路
         *   *  滑动窗口介绍
         *  注意
         *  AC代码
     *  三、螺旋矩阵
     *   *  错误的尝试
         *  思路
         *  注意
         *  AC代码
         *  继承前边循环变量的写法
         *  不继承前边循环变量的做法
     *  四、数组做题思路总结
     *   *  基本知识
         *  解题思路

### 一、有序数组的平方 ###

[题目链接][Link 1]

#### 错误的尝试 ####

一开始尝试双指针+原地完成（即空间复杂度为O（1））。

将所有的情况分成了全部大于等于0，全部小于等于0，有正有负三种情况，提出的对应方案是直接平方、平方并反转【用临时变量交换两端值，但是有三种情况老是同时解决只有一个、偶数个的情况、奇数个情况】、双指针【左边和右边绝对值比较，但是0和0挨着的情况总是需要特殊处理】。虽然这是一次错误的尝试，但是我通过debug、自己发现问题、解决部分问题的能力好像提升了hhhh。

总而言之，这次尝试失败的原因试图通过空间复杂度O(1)解决问题、问题拆分过于复杂。

#### 思路 ####

1.  方法一：暴力求解，先把所有的数组元素平方放回原处，之后调用Arrays.sort进行排序。
2.  方法二：临时数组+双指针方法。
    
    开辟一个临时数组，因为需要非递增序返回，但我们使用双指针找的绝对值/平方结果最大的值，所以我们为这个新数组定义索引，从初值为最后一个下标。
    
    双指针具体操作，左指针和右指针同时比较，找到最大的，如果选中左边的，左边左边加加，反之，右边减减，很显然这是一个循环过程，循环条件为左指针<=右指针即两者是否相遇
    
    最后，再将这个临时数组指向的地址赋给原数组。

#### 注意 ####

1.  平方值最大的寻找，直接用平方比较即可，最好不要再调用Math.abs函数了= \_ =
2.  双指针循环中别忘了改变指针的值
3.  新数组的下标开始从尾部开始

#### AC代码 ####

#### 暴力版本 ####

class Solution {
        
        public int[] sortedSquares(int[] nums) {
        
            for(int i=0;i<nums.length;i++){
        
                nums[i]=nums[i]*nums[i];
            }
            Arrays.sort(nums);
            return nums;
        }
    }

#### 双指针方法 ####

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

### 二、长度最小的子数组 ###

[题目链接][Link 2]

#### 错误的尝试 ####

一开始的思路是List<List>+get(i).size()+进行遍历寻找，但是当时脑子比较懵，想着应该是需要集合吧，应该是吧……

然后就又想，它只问我长度，也就是一个整形值，我为什么非要把结果存起来？？这样不是绕弯路吗？？然后想起来之前看过数组有个解题技巧叫做滑动窗口，然后又想滑动窗口怎么用？怎么滑？然后就没有然后了……

#### 思路 ####

核心解题思路：滑动窗口/双指针

这里我们采用滑动窗口解题，那么就必须要知道什么是滑动窗口，到底怎么使用？

##### 滑动窗口介绍 #####

1.  首先什么是滑动窗口？
    
    滑动窗口就是一种通过不断的**调节子序列**的**起始位置**和**终止位置**，从而得出想要的子区间的数组求解办法，因为区间的滑动像一个窗户/窗口一样，所以我们又叫它滑动窗口。
    
    可以看到这里的关键就是起始位置和终止位置的求解。联想我们的双指针，相信不难得出，其实滑动窗口本质上就是双指针，只不过**双指针关注**的是数组中的两个下标，**是两个点**，而**滑动窗口更关注**的是通过对这两个下标区间的截取，**是两个点确定的一个区间**。
2.  那么滑动窗口问题应该怎么思考，怎么解决呢？
    
    从定义中我们可以看出，滑动窗口其实是由起始位置和终止位置唯一确定的。所以这个问题思考的方向可以聚焦到起始位置和终止位置的求解上。
    
    经过前辈们的总结，我们可以把滑动窗口问题分解成3部分：
    
    1）窗口内是什么？
    
    2）如何移动窗口的起始位置？
    
    3）如何移动窗口的结束位置？

看完滑动窗口的介绍，相信大家对这个已经有了一定的了解，下边我们围绕其中确定滑动窗口的三个步骤来思考这个问题。

1）窗口内是什么？

答：是满足同时满足**是子数组**、**子数组元素和>=targe**t和**长度最短**的子数组。

2）如何移动窗口的起始位置？

定义下标i为起始位置,初始值为0，当前窗口内元素的和>=target，记录长度后，移动起始位置i.

3）如何移动窗口的结束位置？

定义遍历变量j，遍历数组，同时也代表当前窗口的结束位置。

定义变量sum，直至将数组元素值向里边加（起始对应的形象/具象概念也就是窗口不断扩大）。

当sum>=target时，我们能直接把用（当前位置-起始位置+1）作为结果吗？不行，反例如：\[1,1,1,1,100\],target=100，此时我们需要将起始位置向后移动。结果应该是1,而不是5。

那针对上述问题，我们应该怎么处理呢？用if判断可以吗？答不可以，需要用while循环，因为不确定起始位置需要向后移动几次。

经过上述讨论，我们已经可以确定本题的大概解题思路了。

1.定义起始位置i初值为0，定义循环变量j初值为0，范围是0~长度-1。【窗口相关变量】

2.定义sum，用于判断窗口的合法性，定义subList变量得到当前窗口的值，用于和之前的结果进行对比，取较小值，subList的确定需要循环

3.最终的ret初值需要是大于等于数组的长度，不然咱们设个-1，所有的都比咱们的大，就不能正确赋值了，别问，问就是已经栽过了。

#### 注意 ####

1.  ret初值的设置需要是大于等于数组的长度！！！！！
2.  窗口的确定时，每次起始位置向后移动，sum也需要对应的减去对应起始位置的值
3.  不要遗忘，最终窗口达到最大，仍然未满足条件，这个需要特殊处理

以上便是滑动窗口的解法，另外还有一种暴力求解问题的方法，就是双for循环，但是注意此时窗口的确定就不是while循环了,而是if语句。这里就不再说了，因为我这个暴力解法有点晕- -

#### AC代码 ####

class Solution {
        
        public int minSubArrayLen(int target, int[] nums) {
        
            int ret=nums.length;
            int subList=0;
            int sum=0;
            int tag=0;
            for(int i=0,j=0;j<nums.length;j++){
        
                sum+=nums[j];
                while(sum>=target){
        
                    tag=1;
                    subList=j-i+1;
                    ret=ret>subList?subList:ret;
                    sum-=nums[i++];
                }
            }
            if(tag==0){
        
                return 0;
            }
            return ret;
        }
    }

### 三、螺旋矩阵 ###

[题目链接][Link 3]

#### 错误的尝试 ####

之前碰上过这道题，但是因为感觉下标的确定太麻烦了。没写过，即使当时看了题解。

昨天拿到这道题的时候就是想到了大概思路，既然是螺旋的，是圈的，那么我们我们就用个大循环控制圈数，里边写四个小循环控制每条边。但是说起来容易，做起来难，写的一直完全满足解决问题。

之后去看题解，发现，很多人说这道题比较简单，但是自己并不会，而且这个面试中考的也比较多，就突然惊醒了，说要自己动手去推一遍。

最终虽然没有写对，但是确实完成部分了，并且针对一些问题提出了解决方法。

比如说循环时要确定不变量，保证每次处理的情况，每次都是处理左闭右开的区间。

一开始写的是针对行不变还是列不变进行讨论。

再有就是对于奇数情况我们没有办法处理中心坐标的元素，此时我们就需要单独讨论

知道了到底旋转多少圈，不是n圈，而是n/2圈，但是当时又不想再定义临时变量来控制循环的结束

特别好的一点：处理区间、旋转圈数、奇数情况处理都是自己通过debug出来的！！！

#### 思路 ####

这道题，最终AC代码思路有两种

1.  方法一：继承之前的i或者j的状态
    
    1）赋值时，所有的**坐标格式**都写成`a[i][j]`这种形式【可能会是`a[startx][*]`或者`a[*][starty]`这两种形式】
    
    2）循环的控制条件/**圈数判断**：startx<=n/2
    
    3）**循环变量的改变**：每次循环，startx++;starty++为什么同时加？因为前一圈结束后，我们每次需要处理的起始位置都应该是斜对角譬如b的位置，而不是x相邻的a位置
    
    对应的，结束位置也应该是斜对角的位置，而不是相邻的位置，我们这里定义了一个offset，用于表示不同圈数中每个子循环变量的边界。
    
    ![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-sN16iwVq-1668669258587)(F:\\typora插图\\image-20221117145413210.png)\]][img-sN16iwVq-1668669258587_F_typora_image-20221117145413210.png]
    
    4）当奇数情况下，中心位置的元素在第n/2+1圈上，需要单独赋值
    
    1.  方法二：不继承，每次重新定义循环变量
        
        使用`num <= tar`而不是`l < r || t < b`作为迭代条件，是为了解决当`n`为奇数时，矩阵中心数字无法在迭代过程中被填充的问题。
        
        这里是看了力扣上卡佬的代码思路，感觉与自己最初的思路很像，就mark下来了。

#### 注意 ####

1.  奇数情况，中心坐标需要特殊处理
2.  保证每个子循环处理的情况都是一样的，这里应确保处理的都是左闭右开的区间【全集是每行/每列，大小是n】
3.  注意每次不同圈数中怎么控制子循环边界
4.  继承之前状态的代码中后两个子循环注意没有初始表达式。

#### AC代码 ####

#### 继承前边循环变量的写法 ####

class Solution {
        
        public static int[][] generateMatrix(int n) {
        
            int[][] a=new int[n][n];
            int k=0;
            int startx=0,i=0;
            int starty=0,j=0;
            int offset=1;
            while(startx<n/2){
        
                for(j=starty;j<n-offset;j++){
        
                    a[startx][j]=++k;
                }
                for(i=startx;i<n-offset;i++){
        
                    a[i][j]=++k;
                }
                for(;j>starty;j--){
        
                    a[i][j]=++k;
                }
                for(;i>startx;i--){
        
                    a[i][j]=++k;
                }
                startx++;
                starty++;
                offset++;
            }
            if(n%2==1){
        
                a[n/2][n/2]=n*n;
            }
            return a;
        }
    }

#### 不继承前边循环变量的做法 ####

class Solution {
        
        public int[][] generateMatrix(int n) {
        
            int l = 0, r = n - 1, t = 0, b = n - 1;
            int[][] mat = new int[n][n];
            int num = 1, tar = n * n;
            while(num <= tar){
        
                for(int i = l; i <= r; i++) mat[t][i] = num++; // left to right.
                t++;
                for(int i = t; i <= b; i++) mat[i][r] = num++; // top to bottom.
                r--;
                for(int i = r; i >= l; i--) mat[b][i] = num++; // right to left.
                b--;
                for(int i = b; i >= t; i--) mat[i][l] = num++; // bottom to top.
                l++;
            }
            return mat;
        }
    }

### 四、数组做题思路总结 ###

#### 基本知识 ####

内存中的存储

二分法的基本知识：模板、区间类型、循环不变量、区间类型确定的循环条件和更新操作

详见上一篇。

#### 解题思路 ####

1.  双指针（关注某个点）
2.  滑动窗口（关注区间）

另外，需要知道，数组并不能真正**删除元素**，只能通过覆盖的方式，同时注意`i--`。

[Link 1]: https://leetcode.cn/problems/squares-of-a-sorted-array/
[Link 2]: https://leetcode.cn/problems/minimum-size-subarray-sum/
[Link 3]: https://leetcode.cn/problems/spiral-matrix-ii/
[img-sN16iwVq-1668669258587_F_typora_image-20221117145413210.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/79b073a87a3b474e98b6fe3ccde6163e.png