• home > theory > algorithm > leetcode >

    螺旋矩阵(spiral-matrix)解题思路分析与总结

    Author:zhoulujun Date:

    螺旋矩阵 不涉及到什么算法,就是模拟过程,但却十分考察对代码的掌控能力。个人推荐思路就是定义四个边界(左右、上下类似对撞双指针)。当然也可以直接计算所跑圈数,跑圈过程中去思考边界问题

    螺旋矩阵 不涉及到什么算法,就是模拟过程,但却十分考察对代码的掌控能力。

    螺旋矩阵算法题思路解释

    54. 螺旋矩阵 https://leetcode.cn/problems/spiral-matrix/description/

    59. 螺旋矩阵 II https://leetcode.cn/problems/spiral-matrix-ii/description/

    885. 螺旋矩阵 III https://leetcode.cn/problems/spiral-matrix-iii/description/


    已59为例,有非常多解法。

    解法1

    先跑圈缩圈,跑完后处理剩余的单行/列

    function generateMatrix(n) {
      const matrix = new Array(n).fill(null).map(() => new Array(n).fill(null));
      let num = 1;
      let left = 0, right = n - 1, top = 0, bottom = n - 1;
      while (left < right && top < bottom) {//不能越界
        for (let i = left; i < right; i++) {
          matrix[top][i] = num;
          num++;
        }
        for (let i = top; i < bottom; i++) {
          matrix[i][right] = num;
          num++;
        }
        for (let i = right; i > left; i--) {
          matrix[bottom][i] = num;
          num++;
        }
        for (let i = bottom; i > top; i--) {
          matrix[i][left] = num;
          num++;
        }
        left++;top++; right--; bottom--;// 跑完缩圈
      }
      if (top === bottom) {// 剩余的行列
        for (let i = left; i <= right; i++) {
          matrix[top][i] = num;
          num++;
        }
      }else if (left === right) {
        for (let i = top; i <= bottom; i++) {
          matrix[i][left] = num;
          num++;
        }
      }
      return matrix;
    }

    口诀表:

    https://www.bilibili.com/video/BV1jK411H7XJ/

    解法二

    leetcode官方题解,个人觉得没有上面的简洁。

    var generateMatrix = function(n) {
      let num = 1;
      const matrix = new Array(n).fill(0).map(() => new Array(n).fill(0));
      let left = 0, right = n - 1, top = 0, bottom = n - 1;
      while (left <= right && top <= bottom) {
        for (let column = left; column <= right; column++) {
          matrix[top][column] = num;
          num++;
        }
        for (let row = top + 1; row <= bottom; row++) {
          matrix[row][right] = num;
          num++;
        }
        if (left < right && top < bottom) {
          for (let column = right - 1; column > left; column--) {
            matrix[bottom][column] = num;
            num++;
          }
          for (let row = bottom; row > top; row--) {
            matrix[row][left] = num;
            num++;
          }
        }
        left++;top++; right--; bottom--;// 跑完缩圈
      }
      return matrix;
    };


    解题三

    直接看要跑多少圈,从最外圈开始跑,然后填数,直至跑完。

    var generateMatrix = function(n) {
      let startX = startY = 0;   // 起始位置
      let loop = Math.floor(n/2);   // 旋转圈数
      let mid = Math.floor(n/2);    // 中间位置
      let offset = 1;    // 控制每一层填充元素个数
      let count = 1;     // 更新填充数字
      let res = new Array(n).fill(0).map(() => new Array(n).fill(0));
    
      while (loop--) {
        let row = startX, col = startY;
        // 上行从左到右(左闭右开)
        for (; col < n - offset; col++) {
          res[row][col] = count++;
        }
        // 右列从上到下(左闭右开)
        for (; row < n - offset; row++) {
          res[row][col] = count++;
        }
        // 下行从右到左(左闭右开)
        for (; col > startY; col--) {
          res[row][col] = count++;
        }
        // 左列做下到上(左闭右开)
        for (; row > startX; row--) {
          res[row][col] = count++;
        }
    
        // 更新起始位置
        startX++;
        startY++;
    
        // 更新offset
        offset += 1;
      }
      // 如果n为奇数的话,需要单独给矩阵最中间的位置赋值
      if (n % 2 === 1) {
        res[mid][mid] = count;
      }
      return res;
    };

    这个写法,我觉得更加复杂。



    转载本站文章《螺旋矩阵(spiral-matrix)解题思路分析与总结》,
    请注明出处:https://www.zhoulujun.cn/html/theory/algorithm/leetcode/9144.html