Leetcode 977.有序数组的平方

题目：977. 有序数组的平方

初始思路

暴力解法就是先把数组元素全被平方，然后排序即可，时间复杂度取决于排序算法的复杂度。

代码

  1. // 暴力解法
  2. var sortedSquares = function (nums) {
  3.   for (let i = 0; i < nums.length; i++) {
  4.     nums[i] = nums[i] * nums[i]
  5.   }
  6.   nums.sort((a, b) => { return a - b })
  7.   return nums
  8. };
  1. // 双指针法
  2. var sortedSquares = function (nums) {
  3.   let res = new Array(nums.length).fill(0)
  4.   let left = 0
  5.   let right = nums.length - 1
  6.   let index = nums.length - 1
  7.   while (left <= right) {
  8.     let n1 = nums[left] * nums[left]
  9.     let n2 = nums[right] * nums[right]
  10.     if (n1 < n2) {
  11.       res[index] = n2
  12.       index--
  13.       right--
  14.     } else {
  15.       res[index] = n1
  16.       index--
  17.       left++
  18.     }
  19.   }
  20.   return res
  21. }

感想

  1. 暴力解法必要时还是要使用。
  2. 因为数组是有序的，如果原数组有正负数的话，平方后的最大值就在原数组的两端，中间的0肯定是最小的，用双指针从两侧夹。全是负数或者正数的时候也成立。

Leetcode 209.长度最小的子数组

题目：209. 长度最小的子数组 讲解：https://www.bilibili.com/video/BV1tZ4y1q7XE

初始思路

之前没做过滑动窗口的题目，完全没思路，先看了视频讲解，十分清晰。

代码

  1. var minSubArrayLen = function (target, nums) {
  2.     const len = nums.length
  3.     let left = right = sum = 0
  4.     let result = Infinity
  5.     // left是滑动窗口起始位置，暂时不动
  6.     // right向右移动找到符合条件的区间
  7.     while (right < len) {
  8.         // 先求出这段区间的和
  9.         sum += nums[right++]
  10.         while (sum >= target) {
  11.             // 如果满足条件，求出这段区间的长度
  12.             result = Math.min(result,right - left)
  13.             // 滑动窗口起始位置开始向左移动，缩小区间
  14.             // 如果sum一直大于target就可以一直缩小区间
  15.             // 如果小于target了right就向右移动，扩大区间
  16.             sum -= nums[left++]
  17.         }
  18.     }
  19.     return result === Infinity ? 0 : result
  20. };

感想

  1. 首先将窗口起始位置固定，然后right指针向右移动，找到和大于等于target的区间。

在这个区间内部，移动left指针，将区间缩小，如果区间比如原来的长度小就更新结果。
一旦sum小于target，right指针再次右移，找到符合的区间继续收缩。

  1. 在求区间长度的时候很容易出错，right - left到底要不要加一。
  2. 时间复杂度：O(n)

空间复杂度：O(1)

  1. 滑动窗口很有意思，需要多练练。

Leetcode 59.螺旋矩阵II

题目：59. 螺旋矩阵 II 讲解：https://www.bilibili.com/video/BV1SL4y1N7mV/

初始思路

乍一看很简单，不就是一圈圈的赋值嘛，但是写起来很复杂， 不知道如何控制循环，控制赋值。不是翻转矩阵那种找关系的题目，单纯就是一圈圈的赋值。就是暴力解法的思路

代码

  1. // 采用左闭右开
  2. var generateMatrix = function (n) {
  3.     // 起始位置
  4.     let startX = startY = 0
  5.     // 循环次数
  6.     let loop = Math.floor(n / 2)
  7.     // 中间位置 就是n^2在的位置
  8.     let mid = Math.floor(n / 2)
  9.     // 控制每一层填充元素的个数
  10.     let offset = 1
  11.     // 填充的数字
  12.     let count = 1
  13.     // 申请一个二维数组
  14.     let res = new Array(n).fill(0).map(() => new Array(n).fill(0))
  15.     while (loop--) {
  16.         let row = startX
  17.         let col = startY
  18.         // 上 col逐渐变大
  19.         for (; col < startY + n - offset; col++) {
  20.             res[row][col] = count++
  21.         }
  22.         // 右 row逐渐变大
  23.         for (; row < startX + n - offset; row++) {
  24.             res[row][col] = count++
  25.         }
  26.         // 下 col从大变小
  27.         for (; col > startY; col--) {
  28.             res[row][col] = count++
  29.         }
  30.         // 左 row从大变小
  31.         for (; row > startX; row--) {
  32.             res[row][col] = count++
  33.         }
  34.         // 更新起始位置 放到下一圈矩形的左上角
  35.         startX++
  36.         startY++
  37.         // 到下一次内圈，一行元素减少两个
  38.         offset += 2
  39.     }
  40.     // 如果n为奇数，要给n^2单独赋值
  41.     if (n % 2 === 1) {
  42.         res[mid][mid] = n * n
  43.     }
  44.     return res
  45. };

感想

  1. 起始位置startX、startY循环完一圈后都加一，左上角就是下一圈的起始位置。
  2. 因为左闭右开，所以每行填充元素个数是 n - offset。控制每行元素个数的offset循环完一圈之后减二。
  3. 在一圈的运行过程中：col变大 ——> row变大 ——> col回到起始位置 ——> row回到起始位置
  4. 最后需要判断一下中心位置需不需要额外填。