Day2 977.有序数组的平方 209.长度最小的子数组 59.螺旋矩阵II

发表于 更新于 分类于

作业条：https://docs.qq.com/doc/DUGRwWXNOVEpyaVpG

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

第一想法

暴力：计算每个数字的平方，然后整体排序 O（nlogn）
双指针：找到最小值，用两个指针分别指向最小值左边和右边，然后比较两个平方值，小的放入新数组；
双指针分别指向头和尾，比较头尾两个的平方值，较大的放入数组尾部

看完解答后的想法

同上

实现过程中的问题

写数组从小到大排序发现太麻烦了，然后想到了可以从后向前

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

第一想法：

利用滑动窗口和两个指针分别指向窗口第一个位置和结束位置，先将元素加入窗口，判断窗口的和，如果满足条件那么记录下当前的长度；
然后再缩小左边的窗口，如果仍然满足条件，判断和之前的长度取最小长度记录下来。

看完解答后的想法：

同上

实现过程中的问题：

  1. 算法的终止条件是什么？由于算法最后遍历了所有的元素，所以终止条件是其中一个指针（窗口右端）遍历完数组。
  2. 如何组织算法流程？外循环遍历数组，计算元素的和，然后判断是否满足条件，不满足则直接跳出循环进行下一次加入；满足条件的情况下，先记录下当前满足条件的长度，然后尝试缩减长度，记录缩减后并且还满足条件的最小长度；

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/

第一想法：

按照螺旋的顺序依次打印数组，只是知道这个想法，但是具体实现的时候对想法模糊不清。

看完解答后的想法：

  1. 循环终止条件：循环的圈数是n/2，因为每次一圈包含两行/列；注意n如果是奇数的情况，单独处理最后一个数
  2. 每一圈的处理：按照螺旋循环，每次左开右闭
  3. 如何控制每一圈的赋值：使用一个变量标记每圈的起始位置，以及每行/列的终止位置

实现过程中的问题：

每次循环开始都是不固定的，所以每次startx和starty要赋值给i,j；
对奇数矩阵中心数的处理

今日收获和学习时长

1小时18分