59-螺旋矩阵II.md

题目描述

螺旋矩阵II

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

• 示例1:

输入：n = 3

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

分类

中等 矩阵

思路

思路1

/**
 * @param {number} n
 * @return {number[][]}
 */
var generateMatrix = function(n) {
  // 生成储存结果的数组 [[], [], []]
  const resArr = new Array(n).fill(1).map(i => [])
  // 当前应该移动的方式
  // right bottom left up
  let direction = 'right'
  // 列
  let columnIndex = 0;
  // 行
  let rowIndex = 0
  for (let i = 1; i <= n * n; i++) {
    resArr[rowIndex][columnIndex] = i
    switch (direction) {
      case 'right':
        // 已经到末尾，应该转向
        // 到达边界 || 
        if (columnIndex >= n - 1 || resArr[rowIndex][columnIndex + 1]) {
          rowIndex ++
          direction = 'bottom'
        } else {
          columnIndex ++
        }
        break;
      case 'bottom':
        if (rowIndex >= n - 1 || resArr[rowIndex + 1][columnIndex]) {
          columnIndex --
          direction = 'left'
        } else {
          rowIndex ++
        }
        break
      case 'left':
        if (columnIndex <= 0 || resArr[rowIndex][columnIndex - 1]) {
          rowIndex --
          direction = 'up'
        } else {
          columnIndex --
        }
        break
      case 'up':
        if (rowIndex <= 0 || resArr[rowIndex - 1][columnIndex]) {
          columnIndex ++
          direction = 'right'
        } else {
          rowIndex --
        }
        break
    }
  }
  return resArr
};

• 问题分析
  • 整个运行的规则很简单，从左上开始一直向右，遇右界则下，遇下界则左，遇左界则上，遇上界则右。对“界”做一个规则定义：超出边界或者遇到已经经过的元素位置。
  • 这里首先生成储存结果的数组，一个长度为n的，内部填充为[]数组，这里有两个常见的坑
    • resArr = new Array(n).push([])，这样生成的数组中的元素是共用地址，即resArr[0] === resArr[1]，所有的都是相等的。
    • resArr = new Array(n).map(i => [])，由于new Array后，内部是空元素，map方法会忽略掉这些元素，在这里就相当于是没有元素进入map的回调。这里有个奇怪的问题是，map到底会忽略哪种元素，我尝试往数组手动填入undefined，又是能够进入回调的。所以new Array产生的empty item和undefined是什么样的关系？
  • 然后就进行n * n次的遍历，根据边界条件（下一个点位超出 n * n，或者已经有值填入）进行路径规划。