代码随想录算法训练营002| 59. 螺旋矩阵 II，209. 长度最小的子数组，977. 有序数组的平方

59. 螺旋矩阵 II

题目链接：https://leetcode.cn/problems/spiral-matrix-ii/

解题思路

1. 模拟

模拟顺时针画矩阵的过程:(坚持了每条边左闭右开的原则)

填充上行从左到右
填充右列从上到下
填充下行从右到左
填充左列从下到上

代码

/**
 * @param {number} n
 * @return {number[][]}
 */
var generateMatrix = function (n) {
  const res = new Array(n).fill(0).map(() => new Array(n).fill(0));

  let startX = 0,
    startY = 0; // 定义每循环一个圈的起始位置
  let loop = n >> 1; // 每个圈循环几次，例如n为奇数3，那么loop = 1 只是循环一圈，矩阵中间的值需要单独处理
  let mid = n >> 1; // 矩阵中间的位置，例如：n为3， 中间的位置就是(1，1)，n为5，中间位置为(2, 2)
  let count = 1; // 用来给矩阵中每一个空格赋值,填充数字
  let offset = 1; // 需要控制每一条边遍历的长度，每次循环右边界收缩一位
  let i, j;
  while (loop--) {
    // 定义行列
    let i = startX,
      j = startY;

    // 模拟填充上行从左到右（左闭右开）
    for (j = startY; j < n - offset; j++) {
      res[startX][j] = count++;
    }
    // 模拟填充右列从上到下（左闭右开）
    for (i = startX; i < n - offset; i++) {
      res[i][j] = count++;
    }
    /*
     填充完右列时，i和j已经是最大值了，填充下行和左列时不需要初始值
    */

    // 模拟填充下行从右到左（左闭右开）
    for (; j > startY; j--) {
      res[i][j] = count++;
    }
    // 模拟填充左列做下到上（左闭右开）
    for (; i > startX; i--) {
      res[i][j] = count++;
    }

    // 第二圈开始的时候，起始位置要各自加1，例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1)
    startX++;
    startY++;

    // offset 控制每一圈里每一条边遍历的长度
    offset += 1;
  }
  // 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
  if (n % 2) {
    res[mid][mid] = count;
  }
  return res;
};

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

209. 长度最小的子数组

题目链接：https://leetcode.cn/problems/minimum-size-subarray-sum/

解题思路

1. 暴力解法

两个 for 循环，然后不断的寻找符合条件的子序列。

代码

/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function (target, nums) {
  let result = Number.MAX_SAFE_INTEGER; // 最小的连续子数组的长度
  let len = nums.length;
  let sum = 0; // 子序列的数值之和
  let subLength = 0; // 子序列的长度
  for (let i = 0; i < len; i++) {
    // 设置子序列起点为i
    sum = 0; // 每次重新计算和
    for (let j = i; j < len; j++) {
      // 设置子序列终止位置为j
      sum += nums[j];
      if (sum >= target) {
        // 一旦发现子序列和超过target，更新result
        subLength = j - i + 1; // 取子序列的长度
        result = Math.min(result, subLength);
        break; // 因为我们是找符合条件最短的子序列，所以一旦符合条件就break
      }
    }
  }

  // 如果result是Number.MAX_SAFE_INTEGER，就返回0，说明没有符合条件的子序列
  return result === Number.MAX_SAFE_INTEGER ? 0 : result;
};
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

2. 滑动窗口

所谓滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。
窗口就是 满足其和 >= target 的长度最小的连续子数组。
窗口的起始位置如何移动：如果当前窗口的值大于target了，窗口就要向前移动了（也就是该缩小了）。
窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，也就是 for 循环里的索引。

代码

/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function (target, nums) {
  let result = Number.MAX_SAFE_INTEGER; // 最小的连续子数组的长度
  let len = nums.length;
  let sum = 0; // 滑动窗口的数值之和
  let i = 0; // 滑动窗口的起始位置
  let subLength = 0; // 滑动窗口的的长度

  for (let j = 0; j < len; j++) {
    sum += nums[j];
    // 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件
    while (sum >= target) {
      // 一旦发现子序列和超过target，更新result
      subLength = j - i + 1; // 取子序列的长度
      result = Math.min(result, subLength);
      sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）
    }
  }

  // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
  return result == Number.MAX_SAFE_INTEGER ? 0 : result;
};
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

977. 有序数组的平方

题目链接：https://leetcode.cn/problems/squares-of-a-sorted-array/

解题思路

1. 暴力法

每个数平方之后，排序。

代码

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortedSquares = function (nums) {
  for (let i = 0; i < nums.length; i++) {
    nums[i] *= nums[i];
  }
  nums.sort((a, b) => a - b); // 排序
  return nums;
};
1
2
3
4
5
6
7
8
9
10
11

2. API

代码

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortedSquares = function (nums) {
  return nums.map((item) => item * item).sort((a, b) => a - b);
};
1
2
3
4
5
6
7

3. 双指针法

数组其实是有序的, 只不过负数平方之后可能成为最大数了。
那么数组平方的最大值就在数组的两端, 不是最左边就是最右边, 不可能是中间。
此时可以考虑双指针法了, left 指向起始位置, right 指向终止位置。
定义一个新数组 result, 和 A 数组一样的大小, 让 index 指向 result 数组终止位置。

如果 A[left] * A[left] < A[right] * A[right]，那么 result[index--] = A[right] * A[right];

如果 A[left] * A[left] >= A[right] * A[right]，那么 result[index--] = A[left] * A[left];

代码

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortedSquares = function (nums) {
  let len = nums.length;
  let result = new Array(len).fill(0); // 定义一个新数组result，和A数组一样的大小
  let index = len - 1; // 让index指向result数组终止位置

  for (let left = 0, right = len - 1; left <= right; ) {
    if (nums[left] * nums[left] > nums[right] * nums[right]) {
      result[index--] = nums[left] * nums[left]; // 左边的数值大
      left++;
    } else {
      result[index--] = nums[right] * nums[right]; // 右边的数值大
      right--;
    }
  }

  return result;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21