Description

sl1673495

opened on Jun 30, 2020

Issue body actions

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

示例:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/spiral-matrix-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

这题基本上就是和 螺旋矩阵-54 反过来了，54 题是把值按顺序输出出来，这题是按顺序重建二维数组，稍作改动即可完成。

/**
 * @param {number} n
 * @return {number[][]}
 */
let generateMatrix = function (n) {

    // 记录一个 visited 数组
    // 按照 右 -> 下 -> 左 -> 上 的方向不断前进
    // 直到遇到边界或者已经访问过的元素 则切换成下一个方向
    let dirs = [
        [0, 1], // 右
        [1, 0], // 下
        [0, -1], // 左
        [-1, 0], // 上
    ]

    let currentDirIndex = 0

    let visited = []
    for (let y = 0; y < n; y++) {
        visited[y] = []
    }
    let isValid = (y, x) => {
        return y >= 0 && y < n && x >= 0 && x < n && !visited[y][x]
    }

    let targetLength = n * n
    let res = []
    for (let y = 0; y < n; y++) {
        res[y] = []
    }

    let helper = (y, x, num) => {
        res[y][x] = num

        if (num === targetLength) {
            return res
        }

        visited[y][x] = true
        let [diffY, diffX] = dirs[currentDirIndex % 4]
        let nextY = y + diffY
        let nextX = x + diffX
        if (!isValid(nextY, nextX)) {
            [diffY, diffX] = dirs[++currentDirIndex % 4]
            nextY = y + diffY
            nextX = x + diffX
        }
        helper(nextY, nextX, num + 1)
    }

    helper(0, 0, 1)

    return res
};

Activity

1. sl1673495

   added

   递归与回溯

   on Jun 30, 2020
2. Chocolate1999 commented on Sep 11, 2020

   

   Chocolate1999

   on Sep 11, 2020

   More actions

   /**
    * @param {number} n
    * @return {number[][]}
    */
   var generateMatrix = function(n) {
       let top = 0, bottom =n-1
       let left = 0, right = n-1
       let res = []
       for(let i=0;i<n;i++) res[i] = []
       let cur = 1, total = n*n
       while(cur<=total){
           for(let i=left;i<=right;i++) res[top][i] = cur++  // 从左到右
           top++
           for(let i=top;i<=bottom;i++) res[i][right] = cur++ // 从上到下
           right--
           for(let i=right;i>=left;i--) res[bottom][i] = cur++ // 从右到左
           bottom--
           for(let i=bottom;i>=top;i--) res[i][left] = cur++ // 从下到上
           left++
       }
       return res
   };

   Reacted by Choi Yang, bennyli and wonderzhu

   Reacted by zzy-cl
3. bennyli519 commented on Dec 18, 2021

   

   bennyli519

   on Dec 18, 2021

   More actions

   let generateMatrix = function(n) {
       let num = 1;
       let matrix = new Array(n).fill(0).map(() => new Array(n).fill(0));
       let left = 0,right = n-1,bottom = n-1,top =0;
       while(num <= n*n){
           //填充上行从左到右 
           for(let i = left;i<=right;i++){
               matrix[top][i] = num;
               num ++; 
           }
           top++;
           //填充右列从上到下
           for(let i = top;i<=bottom;i++){
               matrix[i][right] = num;
               num++;
           }
           right--;
           //填充下行从右到左
           for(let i = right;i>=left;i--){
               matrix[bottom][i] = num;
               num ++;
           }
           bottom--;
           //填充左列从下到上
           for(let i = bottom;i>=top;i--){
               matrix[i][left] = num;
               num++;
           }
           left++;
       }
       return matrix
   };
4. keer-tea commented on Jan 31, 2023

   

   keer-tea

   on Jan 31, 2023

   More actions

   function fn2(n: number) {
     const matrix = new Array(n).fill(0).map(() => new Array(n).fill(0))
     const total = n * n
     let i = 0, j = 0, count = 2
     matrix[0][0] = 1
     while(count <= total) {
       while(j < n - 1 && matrix[i][j + 1] === 0) matrix[i][++j] = count ++
       while(i < n - 1 && matrix[i + 1][j] === 0) matrix[++i][j] = count ++
       while(j > 0 && matrix[i][j - 1] === 0) matrix[i][--j] = count ++
       while(i > 0 && matrix[i - 1][j] === 0) matrix[--i][j] = count ++
     }
     return matrix
   }

Issue actions