chuck

# 算法笔记第 01 周

本系列致力于将高频的算法题进行回顾与分析，感兴趣的小伙伴请继续阅读吧。

# 二分查找

力扣题目链接 (opens new window)

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
1
2
3
4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
1
2
3
4

提示：

  • 你可以假设 nums 中的所有元素是不重复的。
  • n 将在 [1, 10000]之间。
  • nums 的每个元素都将在 [-9999, 9999]之间。

思路：

搜索给定数组的元素，如果数组是无序的，可以：

  • 直接进行遍历查找，时间复杂度是O(n) 。
  • 数组排序后进行二分查找。

如果数组是有序的，直接二分查找。

本题使用二分查找进行解决。二分查找的前提是元素是有序的。

写二分法，区间的定义一般为两种，左闭右闭即[left, right]，或者左闭右开即[left, right)。

# 左闭右闭写法

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {
  let left = 0; // 左区间位置
  let right = nums.length - 1; // 右区间位置，数组的最后一个元素索引
  while (left <= right) {
    // 由于包括right，因次left === right有意义
    let middle = left + Math.floor((right - left) / 2); // 计算左右区间的中间值，防止大数溢出，同时向下取整
    if (nums[middle] > target) {
      // 如果区间中间值大于目标值，那么索引在左侧
      right = middle - 1; // 此时将右区间置为中间值减去1，因为中间值肯定不是目标值
    } else if (nums[middle] < target) {
      // 如果区间中间值小于目标值，那么索引在右侧
      left = middle + 1; // 将左区间置为中间值加上1，同样因为中间值肯定不是目标值
    } else {
      return middle; // 上述两个条件都不满足，就直接返回中间值这个索引
    }
  }
  return -1; // 当左右区间已经为空，也就是没有元素，意味着目标值不在区间内，直接返回-1
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# 左闭右开写法

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {
  let left = 0;
  let right = nums.length; // 由于是左闭右开区间，因此右区间为数组长度，而不用减一，因为不包括
  while (left < right) {
    // 由于不包括right，因此left === right无意义
    let middle = left + Math.floor((right - left) / 2);
    if (nums[middle] > target) {
      right = middle; // 索引在左侧，因为不包含right，所以直接将middle赋值给right
    } else if (nums[middle] < target) {
      left = middle + 1; // 其余逻辑和左闭右闭相同
    } else {
      return middle;
    }
  }
  return -1;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 总结

左闭右闭即[left, right]，或者左闭右开即[left, right)的不同在于right的处理。

尤其是当right不被包含时，初始化和剪掉右半部分时，都不需要减一，这里一定要注意。

# 搜索插入位置

力扣题目链接 (opens new window)

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 1:

  • 输入: [1,3,5,6], 5
  • 输出: 2

示例 2:

  • 输入: [1,3,5,6], 2
  • 输出: 1

示例 3:

  • 输入: [1,3,5,6], 7
  • 输出: 4

示例 4:

  • 输入: [1,3,5,6], 0
  • 输出: 0

思路：

本题是一个排序数组，可以考虑使用二分法进行搜索。

# 暴力法

当然也可以使用暴力法进行从头遍历，代码如下：

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function (nums, target) {
  let i = 0; // 初始化索引
  while (nums[i] < target) {
    // 循环的终止条件是当前值大于等于目标值
    i++; // 索引递增
  }
  return i; // 最终返回的索引就是目标所在索引或者需要插入的位置索引
};
1
2
3
4
5
6
7
8
9
10
11
12
13
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

# 二分法

下面分析二分法，此处采用左闭右闭[left, right]区间进行二分法查找。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function (nums, target) {
  let left = 0; // 初始化左区间起始值
  let right = nums.length - 1; // 初始化右区间起始值
  while (left <= right) {
    let middle = left + Math.floor((right - left) >> 1); // 计算区间的中间值，并防止溢出
    if (nums[middle] > target) {
      // 如果中间值大于目标值，则意味着索引在左侧
      right = middle - 1; // 将右区间挪到中间索引左侧
    } else if (nums[middle] < target) {
      // 如果中间值小于目标值，则意味着索引在右侧
      left = middle + 1; // 将左区间挪到中间索引右侧
    } else {
      return middle; // 找到了目标值所在索引并返回
    }
  }
  return right + 1; // 这里是与二分查找不同的地方，具体分析如下
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
  • 时间复杂度：O(log n)
  • 空间复杂度：O(1)

分析：

  • 根据题目描述，是返回存在的索引或者适合插入的位置。因此代码除了最后一行，其他就是二分查找的代码。

  • 返回的索引分为四种情况：

    • 目标值比所有值都小，此时应该返回索引0，因为数组头部是适合插入的位置。那么根据二分查找的规则，此时right会不断左移，直到left === right且等于0，然后执行right = middle - 1 ，等价于right = 0 - 1 ，因此最终需要right + 1 ;
    • 目标值比所有值都大，此时应该返回索引nums.length ，因为数组的尾部是适合插入的位置。根据二分查找的规则，此时left 会不断右移，直到left === right 且等于nums.length - 1 ，然后执行 left = middle + 1 。此时right依旧是初始值nums.length - 1，而我们需要插入的位置是nums.length ，因此最终需要right + 1 ；
    • 目标值就是某个索引，这里直接返回的就是middle ；
    • 目标值介于[left, right] ，当left === right 时，循环会终止。此时亦会有两种情况：目标值比中间值小，那么会执行right = middle - 1 ，而需要插入的位置就是此时right所处位置的下一个位置；目标值比中间值大，那么会执行left = middle + 1，而需要插入的位置也是right所处位置的下一个位置，因为right根本没动，是等于middle的，而目标值大于中间值，所以返回的位置就是middle + 1或者right + 1。 综上所述，除去正常找到索引值并返回middle以外，其余直接返回right + 1即可。

# 总结

本题与二分查找不同之处在于需要处理适合插入的位置，而一共需要考虑的就是上述四种情况，只要摸清四种情况返回位置的情况，本题也就迎刃而解了。

# 在排序数组中查找元素的第一个和最后一个位置

力扣题目链接 (opens new window)

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回[-1, -1]。

进阶：你可以设计并实现时间复杂度为 O(log n)的算法解决此问题吗？

示例 1：

  • 输入：nums = [5,7,7,8,8,10], target = 8
  • 输出：[3,4]

示例 2：

  • 输入：nums = [5,7,7,8,8,10], target = 6
  • 输出：[-1,-1]

示例 3：

  • 输入：nums = [], target = 0
  • 输出：[-1,-1]

思路：

本题采用二分法进行查找。需要处理的情况分为以下三种：

  • 目标值比数组所有的值都大或者都小，此时返回[-1, -1]；
  • 目标值存在于数组中，此时返回目标值的左右索引；
  • 目标值介于数组之间但不存在，此时返回[-1, -1]。
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function (nums, target) {
  const getLeftBorder = (nums, target) => {
    let left = 0,
      right = nums.length - 1;
    let leftBorder = -2; // 记录一下leftBorder没有被赋值的情况
    while (left <= right) {
      let middle = left + ((right - left) >> 1);
      if (nums[middle] >= target) {
        // 寻找左边界，nums[middle] == target的时候更新right
        right = middle - 1;
        leftBorder = right;
      } else {
        left = middle + 1;
      }
    }
    return leftBorder;
  };

  const getRightBorder = (nums, target) => {
    let left = 0,
      right = nums.length - 1;
    let rightBorder = -2; // 记录一下rightBorder没有被赋值的情况
    while (left <= right) {
      let middle = left + ((right - left) >> 1);
      if (nums[middle] > target) {
        right = middle - 1;
      } else {
        // 寻找右边界，nums[middle] == target的时候更新left
        left = middle + 1;
        rightBorder = left;
      }
    }
    return rightBorder;
  };

  let leftBorder = getLeftBorder(nums, target);
  let rightBorder = getRightBorder(nums, target);
  // 情况一
  if (leftBorder === -2 || rightBorder === -2) return [-1, -1];
  // 情况二
  if (rightBorder - leftBorder > 1) return [leftBorder + 1, rightBorder - 1];
  // 情况三
  return [-1, -1];
};
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

# 移除元素

力扣题目链接 (opens new window)

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。

示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

你不需要考虑数组中超出新长度后面的元素。

思路：

题目要求要原地修改数组，因此首先想到的是暴利遍历数组的方法。

# 暴力法

先设定变量 idx，指向待插入位置。idx 初始值为 0

然后从题目的「要求/保留逻辑」出发，来决定当遍历到任意元素 x 时，应该做何种决策：

如果当前元素 x 与移除元素 val 相同，那么跳过该元素。 如果当前元素 x 与移除元素 val 不同，那么我们将其放到下标 idx 的位置，并让 idx 自增右移。

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function (nums, val) {
  let idx = 0; // 初始化指针位置
  for (const x of nums) {
    // 当前元素不等于移除元素时，通过自增的idx将数组元素进行覆盖
    // 如果当前元素等于移除元素，则跳过当前元素，同时idx也不自增
    // 最终idx的值就是去除需要移除元素后的数组长度，且新数组中新长度内的元素不包括移除元素
    if (x !== val) nums[idx++] = x;
  }
  return idx;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

# 双指针法

该方法的核心思路是：将需要移除的元素交换至数组的末尾，这样有效数组内就没有需要移除的元素了。

返回有效部分的结尾下标。

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */

// 交换数组元素
const swap = (nums, i, j) => {
  let temp = nums[i];
  nums[i] = nums[j];
  nums[j] = temp;
};

var removeElement = function (nums, val) {
  let j = nums.length - 1; // 右指针初始化指向数组末尾
  for (let i = 0; i <= j; i++) {
    // 终止条件是i大于j
    if (nums[i] === val) {
      // 数组中的元素等于需要移除的元素，则进行交换
      swap(nums, i--, j--); // 先执行元素交换，然后左指针和右指针同时递减
    }
  }
  return j + 1; // 有效部分的下标加1就是新数组的长度
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

说明：

swap(nums, i--, j--) ：此处进行元素的交换，然后左指针和右指针同时递减。这样可以做到：

  • 检查交换后的nums[i]是否等于val ，因为此时的nums[i]是nums[j]交换过来的，并没有进行比较。如果不i-- ，那么就会跳过与val的对比，这显然是不合适的。
  • j-- 是用来前移右指针，用来存储下一个待交换的元素。

# 总结

双指针法（快慢指针法）在数组和链表的操作中是非常常见的，很多考察数组、链表、字符串等操作的面试题，都使用双指针法。

同时需要注意指针的递增和递减，考虑到边界情况。

# 删除有序数组中的重复项

力扣题目链接 (opens new window)

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素只出现一次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

思路：

首先考虑使用双指针法进行删除。

# 双指针法

一个指针 i 进行数组遍历，另外一个指针 j 指向有效数组的最后一个位置。

只有当 i 所指向的值和 j 不一致时，才将 i 的值添加到 j 的下一个位置。

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function (nums) {
  let j = 0; // 有效数组的位置初始化为数组首位
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== nums[j]) {
      // 当遍历的当前值与有效数组的最后一位不相等时
      nums[++j] = nums[i]; // 将当前值添加到有效数组的下一位
    }
  }
  return j + 1; // 返回有效数组的长度
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

解析：

  • 当遍历的值与j相等时，意味着是重复元素，因此不进入判断直接跳过；
  • 当不相等时进入判断，意味着当前值是可以作为有效数组的新元素的。因此将当前值赋值给有效数组的下一位。这里的做法是直接nums[++j] 。
  • 这里是++j而不是j++ ，是因为数组的第0项肯定是不会有重复的，此时需要将遍历的值放入数组的下一个元素，因此先自增 1。
  • 最终返回有效数组的指针加一就是新数组的长度。

# 通用的解法

本题的要求是相同的元素最多出现一次，那么可以发散为最多出现k次。如若如此，那么遵循以下规律：

  • 前k次数字可以直接保留；
  • 后面次数可以保留的前提是，要写入的元素与前k个元素进行比较，不相同则保留。

注意第二条规律，如果说可以最多出现三次，等第四次进行写入的时候，与前三个元素进行比较：如果相同就丢弃，因为不能出现第四次了；如果不相同则保留。

根据上述规律，可以写出如下代码：(参考三叶大神的题解)

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
const generator = (nums, k) => {
  let idx = 0;
  for (const num of nums) {
    if (idx < k || nums[idx - k] !== num) nums[idx++] = num;
  }
  return idx;
};

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function (nums) {
  return generator(nums, 1);
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

解析：

  • 核心还是通过双指针法进行去重，重点需要关注循环内部的逻辑。
  • 当有效数组的末位索引小于k时，我们直接放入有效数组，因为允许k个元素重复。注意这里判断条件是小于，是因为idx是索引，而k是个数，如果相等的话，数组的元素就是k+1 个，此时便无法保证只有k个元素重复。
  • 当超过k个元素时，我们需要将当前需要插入的元素与前k个元素进行比较：如果相等，那么直接跳过，因为已经有k个元素重复了(大前提是数组有序)；如果不相等则将当前值放入有效数组的下一位。
  • 注意这里使用了idx++而不是++idx ，是因为前k次比较是从第一个元素开始的，如果执行++idx，会导致将数组的第一项赋值给数组的第二项，会产生错位。

# 总结

该题的核心思路还是双指针法，要注意自增的时机和返回的值。一般双指针法要循环完整个数组或者链表，并且只需要常数级的变量空间，因此时间复杂度为O(n)，空间复杂度为O(1)。

# 有序数组的平方

力扣题目链接 (opens new window)

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1： 输入：nums = [-4,-1,0,3,10] 输出：[0,1,9,16,100] 解释：平方后，数组变为 [16,1,0,9,100]，排序后，数组变为 [0,1,9,16,100]

示例 2： 输入：nums = [-7,-3,2,3,11] 输出：[4,9,9,49,121]

思路：

首先想到的就是暴力解决，针对数组每项进行平方，然后排序并返回。此方法是可以通过的。

# 暴力法

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

# 双指针法

另一种思路是采用双指针法。由于数组本身是有序的，因此数组项平方后，最大值肯定在数组的两端。此时我们使用双指针分别指向数组的首端和末端，同时开辟一个新的数组，从后往前塞入数据。

分别比较双指针的值的平方，哪个值大就将值塞入新数组。最后返回的新数组就是有序的集合。

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortedSquares = function (nums) {
  const length = nums.length; // 缓存数组参数的长度
  let result = new Array(length); // 声明长度为length的新数组
  let k = length - 1; // 指向新数组末尾的指针
  let i = 0; // 指向nums数组的头部指针
  let j = length - 1; // 指向nums数组的尾部指针
  while (i <= j) {
    // 循环的终止条件是i > j
    let squareI = nums[i] * nums[i]; // 缓存头部指针指向值的平方
    let squareJ = nums[j] * nums[j]; // 缓存尾部指针指向值的平方
    if (squareI < squareJ) {
      // 判断双指针的值的平方，如果尾部指针的值较大
      result[k--] = squareJ; // 则将该值放入新数组末尾，并将新数组指针前移一位
      j--; // 尾部指针的值已经处理过，因此将尾部指针前移一位
    } else {
      // 如果头部指针的值大于等于尾部的值
      result[k--] = squareI; // 则将该值放入新数组末尾，并将新数组指针前移一位
      i++; // 头部指针的值已经处理过，因此将头部指针后移一位
    }
  }
  return 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

# 总结

此题既可以暴力破解，也可以双指针完成。遇见处理有序数组的问题，优先想到双指针，看看可否可以解决。

# 长度最小的子数组

力扣题目链接 (opens new window)

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例：

输入：s = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组。

思路：

首先考虑使用暴力法破解，通过两层循环来累加进行判断。

# 暴力法

/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function (target, nums) {
  let result = Infinity; // 初始化结果为无穷大，方便与循环内的值进行判断
  let sum = 0; // 初始化累加和为0
  let length = nums.length; // 缓存数组长度
  for (let i = 0; i < length; i++) {
    sum = 0; // 每次外层循环清空累加和，方便内层循环进行累加
    for (let j = i; j < length; j++) {
      sum += nums[j]; // 累加内层循环的值
      if (sum >= target) {
        // 判断累加和是否大于等于目标值
        let subLength = j - i + 1; // 如果满足条件，则计算满足条件的数组长度
        result = result > subLength ? subLength : result; // 取两者的较小值来更新结果
        break; // 满足条件则退出内层循环
      }
    }
  }
  return result === Infinity ? 0 : result; // 如果还是初始化的无穷大，则返回0。否则返回数组长度
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
  • 时间复杂度：O(n^2)
  • 空间复杂度：O(1)

# 滑动窗口

本题可以使用滑动窗口的思想来处理。通过动态更新窗口的大小，来获取最小的数组长度。

/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function (target, nums) {
  let result = Infinity; // 初始化结果为无穷大
  let left = 0; // 初始化滑动窗口的左右区间为0
  let right = 0;
  let sum = 0; // 初始化累加和为0
  while (right < nums.length) {
    // 终止条件为右区间大于等于数组长度
    sum += nums[right++]; // 滑动窗口从右区间右移开始，进行数值累加
    while (sum >= target) {
      // 当累加和大于等于目标值时进行result更新
      let subLength = right - left; // 由于右区间会自动递增，因此这里不需要加一
      result = result > subLength ? subLength : result; // 选取较小值更新结果
      sum -= nums[left++]; // 累加和满足条件后，将左区间右移，并减去左区间当前值，直到不满足条件后进行下一次外层循环
    }
  }
  return result === Infinity ? 0 : result; // 如果还是初始化的无穷大，则返回0。否则返回数组长度
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

# 总结

使用滑动窗口处理数组，可以将时间复杂度由O(n^2)降低到O(n) ，滑动窗口本质还是双指针法，左右区间的边界要做好处理。

# 螺旋矩阵 II

力扣题目链接 (opens new window)

给定一个正整数n，生成一个包含 1 到n^2所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。

示例:

输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]

思路：

本题的难点在于如何将元素按照顺时针螺旋排列。题解思路参考 Krahets 给出的方案。

  • 生成一个 n×n 空矩阵 mat，随后模拟整个向内环绕的填入过程：
    • 定义当前左右上下边界 l,r,t,b，初始值 num = 1，迭代终止值 tar = n * n；
    • 当 num <= tar 时，始终按照 从左到右 从上到下 从右到左 从下到上 填入顺序循环，每次填入后：
      • 执行 num += 1：得到下一个需要填入的数字；
      • 更新边界：例如从左到右填完后，上边界 t += 1，相当于上边界向内缩 1。
    • 使用num <= tar而不是l < r || t < b作为迭代条件，是为了解决当n为奇数时，矩阵中心数字无法在迭代过程中被填充的问题。
  • 最终返回 mat 即可。
/**
 * @param {number} n
 * @return {number[][]}
 */
var generateMatrix = function (n) {
  let num = 1; // 初始值
  let tar = n * n; // 终止值
  let l = 0; // 左边界初始值
  let r = n - 1; // 右边界初始值
  let t = 0; // 上边界初始值
  let b = n - 1; // 下边界初始值
  let arr = new Array(n).fill(0).map(() => new Array(n).fill(0)); // 声明n * n二维数组
  while (num <= tar) {
    // 迭代条件
    for (let i = l; i <= r; i++) arr[t][i] = num++; // 从左到右更新上边界那一行的每个值
    t++; // 上边界向下缩进
    for (let i = t; i <= b; i++) arr[i][r] = num++; // 从上到下更新右边界那一列的每个值
    r--; // 右边界向左缩进
    for (let i = r; i >= l; i--) arr[b][i] = num++; // 从右到左更新下边界那一行的每个值
    b--; // 下边界向上缩进
    for (let i = b; i >= t; i--) arr[i][l] = num++; // 从下到上更新左边界那一列的每个值
    l++; // 左边界向右缩进
  }
  return arr; // 返回二维数组(矩阵)
};
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

# 总结

本题没有什么数据结构，考察处理问题的思维能力。

算法笔记第 02 周