前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >螺旋矩阵(I、II)

螺旋矩阵(I、II)

作者头像
木子星兮
发布2020-07-17 10:33:08
6180
发布2020-07-17 10:33:08
举报
文章被收录于专栏:前端小码农

螺旋矩阵

题目描述

给定一个包含 m x n 个元素的矩阵(m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素。

示例 1:

代码语言:javascript
复制
输入:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]

示例 2:

代码语言:javascript
复制
输入:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]

解题方法

设置四个边界,四个方向,一个方向只能更改一个坐标值。

  • 在画图分析后,判断出路线都是有固定方向的 先→再↓再←再↑再→.....一直循环到没数字
  • 因此定义4个方向边界 当触及边界时即按固定方向转向 且其对应的边界值向内收缩1
  • 若没触及边界 即按自身方向继续行走 改变坐标值直到触边界/数字全部遍历过
代码语言:javascript
复制
/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var spiralOrder = function(matrix) {
    let result = [];
    if(matrix.length === 0) {
        return result;
    }
    let m = matrix.length;
    let n = matrix[0].length;
    let maxCount = m * n;

    // 定义四个边界
    let boundTop = 0; // 上边界
    let boundBottom = m - 1; // 下边界
    let boundLeft = 0; // 左变界
    let boundRight = n - 1; // 右边界
    // 定义四个方向,根据不同状态进行切换
    // 如果右边界为0(只有1个值),则初始化方向为下
    let direction = boundRight === 0 ? "down" : 'right'; 
    let i = 0;  // 列坐标
    let j = 0; // 行坐标

    for(let k = 0; k < maxCount; k++) {
        result.push(matrix[i][j]);
        /**
         * 1. 在其方向为右 且未触碰边界值时 列向右走(j++)
         * 2. 当触碰时转向,应该向下走,且上边界加1
         */
        if(direction === 'right') {
            j++;
            if(j === boundRight) {
                direction = 'down';
                boundTop++;
            }
        }
        /**
         * 1. 在其方向为下 且未触碰边界值时 向下走(i++)
         * 2. 当触碰时转向,应该向左走,且右边界减1
         */
        else if(direction === 'down') {
            
            i++;
            if(i === boundBottom) {
                direction = 'left';
                boundRight--;
            }
        }
        /**
         * 1. 在其方向为左 且未触碰边界值时 向左走(j--)
         * 2. 当触碰时转向,应该向上走,且下边界减1
         */
        else if(direction === 'left') {
            j--;
            if(j === boundLeft) {
                direction = 'up';
                boundBottom--;
            }
        }
        /**
         * 1. 在其方向为上 且未触碰边界值时 向上走(i--)
         * 2. 当触碰时转向,应该向右走,且左边界加1
         */
        else if(direction === 'up') {
            i--;
            if(i === boundTop) {
                direction = 'right';
                boundLeft++;
            }
        }
    }
    return result;

};

螺旋矩阵II

题目描述

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

示例:

代码语言:javascript
复制
输入: 3
输出:
[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

解题方法

和 螺旋矩阵的解法类似,只不过现在是要将数组打印出来。

代码语言:javascript
复制
/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var generateMatrix = function(n) {
    if(n === 0) {
        return [];
    }
    // 初始化
    let result = new Array(n);
    for(let i = 0; i < n; i++) {
        result[i] = [];
    }
    let maxCount = n * n;
    // 定义四个边界
    let boundTop = 0; // 上边界
    let boundBottom = n - 1; // 下边界
    let boundLeft = 0; // 左变界
    let boundRight = n - 1; // 右边界
    // 定义四个方向,根据不同状态进行切换
    // 如果右边界为0(只有1个值),则初始化方向为下
    let direction = boundRight === 0 ? "down" : 'right'; 
    let i = 0;  // 列坐标
    let j = 0; // 行坐标
    for(let k = 1; k <= maxCount; k++) {
        // 进行赋值
        result[i][j] = k;
        /**
         * 1. 在其方向为右 且未触碰边界值时 列向右走(j++)
         * 2. 当触碰时转向,应该向下走,且上边界加1
         */
        if(direction === 'right') {
            j++;
            if(j === boundRight) {
                direction = 'down';
                boundTop++;
            }
        }
        /**
         * 1. 在其方向为下 且未触碰边界值时 向下走(i++)
         * 2. 当触碰时转向,应该向左走,且右边界减1
         */
        else if(direction === 'down') {
            i++;
            if(i === boundBottom) {
                direction = 'left';
                boundRight--;
            }
        }
        /**
         * 1. 在其方向为左 且未触碰边界值时 向左走(j--)
         * 2. 当触碰时转向,应该向上走,且下边界减1
         */
        else if(direction === 'left') {
            j--;
            if(j === boundLeft) {
                direction = 'up';
                boundBottom--;
            }
        }
        /**
         * 1. 在其方向为上 且未触碰边界值时 向上走(i--)
         * 2. 当触碰时转向,应该向右走,且左边界加1
         */
        else if(direction === 'up') {
            i--;
            if(i === boundTop) {
                direction = 'right';
                boundLeft++;
            }
        }
    }
    return result;

};
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-05-26,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 牧码的星星 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 螺旋矩阵
    • 题目描述
      • 解题方法
      • 螺旋矩阵II
        • 题目描述
          • 解题方法
          领券
          问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档