刷题日记 Day 2 : Leetcode 977 . 有序数组的平方、Leetcode 209 . 长度最小的子数组、Lettcode 59 : 螺旋数组 II

我就是我 2024-03-25 17:54 3阅读 0赞

#### 刷题日记 Day 2 ####

*  一 . Leetcode 977 . 有序数组的平方
 *  二 . Leetcode 209 . 长度最小的子数组
 *  三 . Lettcode 59 : 螺旋数组 II

> 本篇文章 , 是在代码随想录 60 天编程挑战的基础上进行的题目讲解  
> 参与链接在此 : [https://programmercarl.com/other/xunlianying.html][https_programmercarl.com_other_xunlianying.html]

> 大家好 , 这个专栏 , 给大家带来的是 60 天刷题强训 . 最令大家头疼的事就是刷题了 , 题目又臭又长又抽象 , 有的题读都读不懂 , 更别说做了 . 所以 , 这个专栏想要帮助大家摆脱困境 , 横扫饥饿 , 做回自己 . 让大家掌握最常见的面试题 , 面对陌生的题目也不至于无从下手 .  
> 也希望大家监督 , 60 天从 0 到 1 , 咱们一起做大佬 ~  
> 今天是 Day2 , 大家加油~  
> ![image.png][]  
> 专栏链接 : [https://blog.csdn.net/m0\_53117341/category\_12247938.html?spm=1001.2014.3001.5482][https_blog.csdn.net_m0_53117341_category_12247938.html_spm_1001.2014.3001.5482]  
> 昨天的打卡链接 : [http://t.csdn.cn/ggBk1][http_t.csdn.cn_ggBk1]

## 一 . Leetcode 977 . 有序数组的平方 ##

题目链接  
[977. 有序数组的平方][977.]  
![image.png][image.png 1]

这道题 , 暴力方法非常好想出来 , 首先 , 我们可以将数组中所有元素都转成正数 (对负数元素取相反数) , 然后对此时的数组进行排序 , 排序之后我们就可以把每个元素平方 , 就通过这道题了

class Solution {
        
        public int[] sortedSquares(int[] arr) {
        
            // 1. 对数组中负数元素取相反数,让他变成正数
            for(int i = 0;i < arr.length;i++) {
        
                if(arr[i] < 0) {
        
                    arr[i] = - arr[i];
                }
            }
            // 现在所有元素都是正数了
    
            // 2. 对数组进行排序
            Arrays.sort(arr);
    
            // 3. 将每个元素平方,放回到原数组中
            for(int i = 0;i < arr.length;i++) {
        
                int tmp = arr[i];
                arr[i] = (tmp * tmp);
            }
            return arr;
        }
    }

那么这道题 , 最妙的办法就是双指针算法  
我们来看图~  
![image.png][image.png 2]

那双指针思路的有序数组的平方也非常好实现了 , 代码就在这里

class Solution {
        
        public int[] sortedSquares(int[] arr) {
        
            // 1. 定义一个答案数组
            int[] ans = new int[arr.length];
            // 2. 定义一个 k 下标用来操控 ans 数组
            // 注意:k下标要从数组最后开始,因为 arr 数组平方之后两边元素大中间元素小,我们就先把元素大的放到数组右边
            int k = arr.length - 1;
    
            // 3. 定义双指针,让他指向左右两侧
            int i = 0;
            int j = arr.length - 1;
    
            // 4. 左右两边不断比较平房之后的大小,谁大谁先加到答案数组中
            while(i <= j) {
        
                // 先对左右两边平方
                int t1 = arr[i] * arr[i];
                int t2 = arr[j] * arr[j];
                if(t1 >= t2) {
         // 左边大,就把左边平方的结果放到答案数组
                    ans[k--] = t1;// 别忘了添加完元素,答案数组要往前移
                    i++;// 左指针往后移
                } else {
         // 右边大,就把右边平方的结果放到答案数组
                    ans[k--] = t2;
                    j--;// 右指针往前移
                }
            }
            
            return ans;
        }
    }

## 二 . Leetcode 209 . 长度最小的子数组 ##

题目链接 : [209. 长度最小的子数组][209.]  
![image.png][image.png 3]  
这道题 , 是双指针算法的一道变种题 , 通过两个指针之间范围的不断变化模拟出来了滑动的窗口的感觉 , 我们来看图  
![image.png][image.png 4]  
其实光看文字讲解 , 很秀涩难懂  
大家可以跳转到此链接 , 查看视频讲解 : [https://www.bilibili.com/video/BV1tZ4y1q7XE/?spm\_id\_from=333.788&vd\_source=b0e82af8eb60883fa2180dda1770795d][https_www.bilibili.com_video_BV1tZ4y1q7XE_spm_id_from_333.788_vd_source_b0e82af8eb60883fa2180dda1770795d]  
代码也给大家贴到这里了

class Solution {
        
        public int minSubArrayLen(int target, int[] arr) {
        
            // 1. 定义几个滑动窗口需要的变量
            // 滑动窗口的起点
            int i = 0;
            // 滑动窗口内所有元素的值
            int sum = 0;
            // 答案(满足其和 ≥ target 的长度最小的 连续子数组 的长度)
            int result = Integer.MAX_VALUE;
            // 当前滑动窗口长度
            int nowLength = 0;
    
            // 用 j 表示滑动窗口的终点
            // 先让 j 往后移动找到滑动窗口里面的和大于 sum 的那个点
            for(int j = 0;j < arr.length;j++) {
        
                sum += arr[j];
                // 接下来让 i 往后移动,不断缩小范围
                while(sum >= target) {
        
                    // 统计一下当前滑动窗口大小
                    nowLength = j - i + 1;
                    // 更新 result
                    result = Math.min(nowLength,result);
                    // 更新完之后第一个值就可以剔除掉了
                    sum -= arr[i];
                    // i 往后移动
                    i++;
                }
            }
    
            // 最后返回的结果要注意
            // target = 11, nums = [1,1,1,1,1,1,1,1]
            // 这种情况,result就没更新,所以我们需要判定一下,如果 result 还是默认最大值,就让他返回 0 即可
            return result == Integer.MAX_VALUE ? 0 : result;
        }
    }

## 三 . Lettcode 59 : 螺旋数组 II ##

题目链接 : [59. 螺旋矩阵 II][59. _ II]  
![image.png][image.png 5]  
这道题 , 真的是非常可恨的一道题 !  
它的边界处理条件很麻烦 , 而且思路必须非常明确才能保证不写错  
对付这种难题 , 最好的办法就是画图  
首先 , 我们要明确一件事 : **循环不变量**  
这是什么意思呢 ?  
我们在进行边界处理的时候 , 很容易就乱套 , 比如这样  
![image.png][image.png 6]  
我们用四种颜色 , 划分了四个区间 , 有左闭右闭的 , 比如 橙色区间 ; 有左开又开的 , 比如 : 绿色区间、灰色区间 ; 有左开右闭的 , 比如 : 褐色区间 ; 这样的话 , 又是左开右闭的 , 又是左闭右开的 , 就很容易给咱们搞乱 .  
所以咱们统一规则 : 统一采取左闭右开的方式来螺旋  
![image.png][image.png 7]  
我们可以看到 , 四个颜色都是左闭右开原则 , 这样就不容易给我们搞乱  
那我们接下来看具体的例子  
![image.png][image.png 8]  
那大家一定要画图好好理解一下  
代码就在下面了

class Solution {
        
        public int[][] generateMatrix(int n) {
        
            // 1. 定义答案数组,将螺旋的值都添加到矩阵中
            int[][] ans = new int[n][n];
            // 2. 定义变量:圈数/2,它是与循环条件有关的
            int loop = n / 2;
            // 3. 定义 startx starty 变量,表示每循环一个圈的起始位置
            int startx = 0;
            int starty = 0;
            // 4. 定义 offset 表示for循环的条件的处理
            int offset = 1;
            // 5. 通过不断自增表示每一个元素的值
            int count = 1;// 初始值为1
            int i = 0;
            int j = 0;
    
            // 循环条件:圈数/2
            // 每循环完一圈,就要--一下,不要忘了
            while(loop -- != 0) {
        
                // 第一行
                for(j = starty;j < n - offset;j++) {
        
                    ans[startx][j] = count++;
                }
                // 最后一列
                for(i = startx;i < n - offset;i++) {
        
                    ans[i][j] = count++;
                }
                // 最后一行
                for(;j > starty;j--) {
        
                    ans[i][j] = count++;
                }
                // 第一列
                for(;i > startx;i--) {
        
                    ans[i][j] = count++;
                }
                // 最后更新startx starty 为新的一圈的起点
                startx++;
                starty++;
                // for 循环条件也需要改动一下,不然就访问过油子了
                offset++;
            }
    
            // 最后额外判定一下,n是奇数还是偶数
            // n 是奇数的话,最中间的那个元素就访问不到,需要我们手动赋值
            if(n % 2 != 0) {
        
                ans[n/2][n/2] = count;
            }
            return ans;
        }
    }

--------------------

总体来说 , 今天题目的难度略高 , 大家耐心体会 , 如果阅读博客还是不理解的话 , 可以在 B 站上搜索 程序员卡尔 , 有详细的视频讲解  
![image.png][image.png 9]

[https_programmercarl.com_other_xunlianying.html]: https://programmercarl.com/other/xunlianying.html
[image.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/01e64c91325547c9a081315b10667a15.png
[https_blog.csdn.net_m0_53117341_category_12247938.html_spm_1001.2014.3001.5482]: https://blog.csdn.net/m0_53117341/category_12247938.html?spm=1001.2014.3001.5482
[http_t.csdn.cn_ggBk1]: http://t.csdn.cn/ggBk1
[977.]: https://leetcode.cn/problems/squares-of-a-sorted-array/
[image.png 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/604711409b514e4eb0a630a3722bd423.png
[image.png 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/810df546e5164ada96114a4036f06010.png
[209.]: https://leetcode.cn/problems/minimum-size-subarray-sum/
[image.png 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/4368ff1d36c54c078b54ec6616cc7bd0.png
[image.png 4]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/e3fdd8b4d5d84ca4b6d8a1ed7408dbba.png
[https_www.bilibili.com_video_BV1tZ4y1q7XE_spm_id_from_333.788_vd_source_b0e82af8eb60883fa2180dda1770795d]: https://www.bilibili.com/video/BV1tZ4y1q7XE/?spm_id_from=333.788&vd_source=b0e82af8eb60883fa2180dda1770795d
[59. _ II]: https://leetcode.cn/problems/spiral-matrix-ii/
[image.png 5]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/d10608c86edf48cf84c6971bc980671d.png
[image.png 6]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/c37d285adfe24011b45a96d47f142b96.png
[image.png 7]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/791624fc2ca74d219fcc5ab9f95fcd28.png
[image.png 8]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/678b0539e0da4fd0a384e684282c76a6.png
[image.png 9]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/81770dfac1d74260ab95eb8016e7a604.png