看一看：一道字节笔试题，没有想到考察的是....

大家好，我是TianTian。

分享的内容是字节的笔试题，字节的算法题。

考察的点，可以归纳于深度优先遍历，或者说是一道脑筋急转弯题。

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

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

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

基本上围绕的思路就是:一层层向里处理，按顺时针依次遍历：上、右、下、左。

其实很类似于迷宫的走法，走到格子后，判断下一个格子，还能不能走，也就是边界条件。遇到边界条件后，顺着上面的顺序: 上、右、下、左。

所以我们可以有几个约束条件:

• 是不是在这个范围内2006年盖的违建房会被强拆吗，不能超过这些范围。
• 这个格子是不是走过，存一下之前的状态。
• 记录当前方向，抱着下一个方向是对的。

按照深度优先遍历思路来写，我们可以构造常见的dfs模版:

constspiralOrder=function(matrix){
if(matrix.length===0)return[];
constresult=[],
dx=[0,1,0,-1],
dy=[1,0,-1,0],
col=matrix.length,
row=matrix[0].length;
//isCheckMatrix记录是否走过
constisCheckMatrix=Array.from(newArray(col),()=>(newArray(row).fill(false)))
constdfs=(x,y,directionIndex)=>{
//逻辑代码
//通常这里做逻辑处理，边界处理
}
};
dfs(0,0,0);
returnresult
};

这应该就是基础的模版，唯一不同的是，我们看dfs的三个参数，x,y,directionIndex。

x和y参数很好理解，这个directionIndex参数含义就是告诉我们当前前进的方向。

接下来，是写我们的逻辑部分。首先确定接下来走到哪一个格子:

dx=[0,1,0,-1]
dy=[1,0,-1,0]
constnextX=x+dx[directionIndex]
constnextY=y+dy[directionIndex]

根据当前的格子所在的位置x,y我们就知道接下来要走的位置，通过directionIndex的下标索引，知道我们下一个格子的坐标。

然后就是判断一下，边界的情况：

• 不能出界
• 判断能不能走

根据以上的信息，其实我们主要的逻辑部分就完成啦。

constspiralOrder=function(matrix){
if(matrix.length===0)return[];
constresult=[],
dx=[0,1,0,-1],
dy=[1,0,-1,0],
col=matrix.length,
row=matrix[0].length;
constisCheckMatrix=Array.from(newArray(col),()=>(newArray(row).fill(false)))
constdfs=(x,y,directionIndex)=>{
result.push(matrix[x][y])//存答案
isCheckMatrix[x][y]=true//标记走过
for(leti=0;i<3;i++){
constnextX=x+dx[directionIndex]
constnextY=y+dy[directionIndex]
//判断边界
if(nextX<col&&nextX>=0&&nextY<row&&nextY>=0&&!isCheckMatrix[nextX][nextY]){
dfs(nextX,nextY,directionIndex)
}
//方向取余数
directionIndex=(directionIndex+1)%4;
}
};
dfs(0,0,0);
returnresult
};

这里我们需要对方向做余数处理。在确只有四个方向的情况，并且在这个方向不能走的情况下，尝试下一个方向。

directionIndex=(directionIndex+1)%4;

写完的时候，我在想能不能优化一下，做个减枝的处理，后面发现城管拆除违章建筑流程，当前这个位置可以走的话，是不是就不能判断其他方向了。

或者说我们可以提前走出这个循环，这里做的优化就是return 当前的处理。

constspiralOrder=function(matrix){
if(matrix.length===0)return[];
constresult=[],
dx=[0,1,0,-1],
dy=[1,0,-1,0],
col=matrix.length,
row=matrix[0].length;
constisCheckMatrix=Array.from(newArray(col),()=>(newArray(row).fill(false)))
constdfs=(x,y,directionIndex)=>{
result.push(matrix[x][y]);
isCheckMatrix[x][y]=true
for(leti=0;i<3;i++){
constnextX=x+dx[directionIndex]
constnextY=y+dy[directionIndex]
if(nextX<col&&nextX>=0&&nextY<row&&nextY>=0&&!isCheckMatrix[nextX][nextY]){
returndfs(nextX,nextY,directionIndex)
}
directionIndex=(directionIndex+1)%4;
}
};
dfs(0,0,0);
returnresult
};

后面发现这个是一道leetcode中等的题目，题目链接:

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