1. 首页
  2. LeetCode 刷题网

LeetCode 054. 螺旋矩阵

题目描述:

难度:Middle

相关话题:数组

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

示例1:

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

示例2:

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

思路:

  • 模拟+DFS

最直观的思路就是模拟这个旋转的过程,定义4个方向,就是顺时针方向,这里我使用dfs,对于当前方向,计算能走的步数limit,走到底,然后换下一个方向,
直到当前方向能走的步数limit为0。

/**
 * @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍:前端中文网是以前端进阶资源教程分享为主的专业网站,包括:前端、大厂面试题、typescript教程、程序人生、React.js
 * @param {number[][]} matrix
 * @return {number[]}
 */
var spiralOrder = function(matrix) {
  if(matrix.length===0)return []
  let rl=matrix[0].length,cl=matrix.length-1
  let res=[]
  let moves=[[0,1],[1,0],[0,-1],[-1,0]]
  let mID=0
  function dfs([x,y]){
    let limit
    if(mID===0 || mID===2) limit=rl--
    else limit=cl--
    if(limit<=0)return
    let [dx,dy]=moves[mID]
    if(++mID===4)mID=0
    let nx=x+dx,ny=y+dy
    while(limit-->0){
      res.push(matrix[nx][ny])
      nx+=dx
      ny+=dy
    }
    dfs([nx-dx,ny-dy])
  }
  dfs([0,-1])
  return res
};
  • 层叠

官方解答的做法,思路很清晰。

就像剥洋葱一样,将当前矩阵一层一层剥掉,例如:

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

数字代表遍历的顺序,也就是加入结果的顺序,很明了而且很有规律,定义4个变量t,d,l,r,分别表示当前上下左右边界,
每剥掉一层对应的t--;d++;l++;r--,直到d<t || r<l

/**
 * @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍:一个致力于帮助开发者用代码改变世界为使命的平台,每天都可以在这里找到技术世界的头条内容
 * @param {number[][]} matrix
 * @return {number[]}
 */
var spiralOrder = function(matrix) {
  if(matrix.length===0)return []
  let m=matrix.length,n=matrix[0].length
  let l=0,r=n-1,t=0,d=m-1
  let res=[]
  while(r-l>=0 && d-t>=0){
    for(let i=l;i<=r;i++)res.push(matrix[t][i])
    for(let i=t+1;i<=d;i++)res.push(matrix[i][r])
    if(d>t){
      for(let i=r-1;i>=l+1;i--)res.push(matrix[d][i])
    }
    if(r>l){
      for(let i=d;i>=t+1;i--)res.push(matrix[i][l])
    }

    l++;r--;t++;d--
  }
  return res
};

看完两件小事

如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:

  1. 关注我们的 GitHub 博客,让我们成为长期关系
  2. 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
  3. 关注公众号 「IT平头哥联盟」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程

JS中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。欢迎热爱技术的你一起加入交流与学习,JS中文网的使命是帮助开发者用代码改变世界

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com

标题:LeetCode 054. 螺旋矩阵

链接:https://www.javascriptc.com/4414.html

« LeetCode 055. 跳跃游戏
DataWorks 如何撑起阿里 99% 的数据开发?»
Flutter 中文教程资源

相关推荐

QR code