题目描述:
难度: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
};
看完两件小事
如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:
- 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
- 关注公众号 「画漫画的程序员」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程
本文著作权归作者所有,如若转载,请注明出处
转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com