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

一、有序数组的平方

题目链接

错误的尝试

一开始尝试双指针+原地完成（即空间复杂度为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;
    }
}
1
2
3
4
5
6
7
8
9

双指针方法

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

二、长度最小的子数组

题目链接

错误的尝试

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

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

思路

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

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

滑动窗口介绍

1. 首先什么是滑动窗口？

   滑动窗口就是一种通过不断的调节子序列的起始位置和终止位置，从而得出想要的子区间的数组求解办法，因为区间的滑动像一个窗户/窗口一样，所以我们又叫它滑动窗口。

   可以看到这里的关键就是起始位置和终止位置的求解。联想我们的双指针，相信不难得出，其实滑动窗口本质上就是双指针，只不过双指针关注的是数组中的两个下标，是两个点，而滑动窗口更关注的是通过对这两个下标区间的截取，是两个点确定的一个区间。

2. 那么滑动窗口问题应该怎么思考，怎么解决呢？

   从定义中我们可以看出，滑动窗口其实是由起始位置和终止位置唯一确定的。所以这个问题思考的方向可以聚焦到起始位置和终止位置的求解上。

   经过前辈们的总结，我们可以把滑动窗口问题分解成3部分：

   1）窗口内是什么？

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

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

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

1）窗口内是什么？

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

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

三、螺旋矩阵

题目链接

错误的尝试

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

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

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

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

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

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

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

知道了到底旋转多少圈，不是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，用于表示不同圈数中每个子循环变量的边界。

   

   4）当奇数情况下，中心位置的元素在第n/2+1圈上，需要单独赋值

   2. 方法二：不继承，每次重新定义循环变量

      使用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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

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

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
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

四、数组做题思路总结

基本知识

内存中的存储

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

详见上一篇。

解题思路

1. 双指针（关注某个点）

2. 滑动窗口（关注区间）

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