一道字节笔试题，没有想到考察的是....
点击上方关注 TianTianUp，一起学习，天天进步
大家好，我是TianTian。
分享的内容是字节的笔试题，字节的算法题。
考察的点，可以归纳于深度优先遍历，或者说是一道脑筋急转弯题。
题目
给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。
输入：
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
输出:
[1,2,3,6,9,8,7,4,5]
思路
基本上围绕的思路就是:一层层向里处理，按顺时针依次遍历：上、右、下、左。
其实很类似于迷宫的走法，走到格子后，判断下一个格子，还能不能走，也就是边界条件。遇到边界条件后，顺着上面的顺序: 上、右、下、左。
所以我们可以有几个约束条件:
是不是在这个范围内，不能超过这些范围。 这个格子是不是走过，存一下之前的状态。 记录当前方向，抱着下一个方向是对的。
深度优先遍历
按照深度优先遍历思路来写，我们可以构造常见的dfs模版:
const spiralOrder = function (matrix) {
if (matrix.length === 0) return [];
const result = [],
dx = [0, 1, 0, -1],
dy = [1, 0, -1, 0],
col = matrix.length,
row = matrix[0].length;
// isCheckMatrix记录是否走过
const isCheckMatrix = Array.from(new Array(col), () => (new Array(row).fill(false)))
const dfs = (x, y, directionIndex) => {
// 逻辑代码
// 通常这里做逻辑处理，边界处理
}
};
dfs(0, 0, 0);
return result
};
这应该就是基础的模版，唯一不同的是，我们看dfs的三个参数，x,y,directionIndex。
x和y参数很好理解，这个directionIndex参数含义就是告诉我们当前前进的方向。
接下来，是写我们的逻辑部分。首先确定接下来走到哪一个格子:
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
const nextX = x + dx[directionIndex]
const nextY = y + dy[directionIndex]
根据当前的格子所在的位置x,y我们就知道接下来要走的位置，通过directionIndex的下标索引，知道我们下一个格子的坐标。
然后就是判断一下，边界的情况：
不能出界 判断能不能走
根据以上的信息，其实我们主要的逻辑部分就完成啦。
代码:
const spiralOrder = function (matrix) {
if (matrix.length === 0) return [];
const result = [],
dx = [0, 1, 0, -1],
dy = [1, 0, -1, 0],
col = matrix.length,
row = matrix[0].length;
const isCheckMatrix = Array.from(new Array(col), () => (new Array(row).fill(false)))
const dfs = (x, y, directionIndex) => {
result.push(matrix[x][y]) // 存答案
isCheckMatrix[x][y] = true // 标记走过
for (let i = 0; i < 3; i++) {
const nextX = x + dx[directionIndex]
const nextY = 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);
return result
};
这里我们需要对方向做余数处理。在确只有四个方向的情况，并且在这个方向不能走的情况下，尝试下一个方向。
directionIndex = (directionIndex + 1) % 4;
优化
写完的时候，我在想能不能优化一下，做个减枝的处理，后面发现，当前这个位置可以走的话，是不是就不能判断其他方向了。
或者说我们可以提前走出这个循环，这里做的优化就是return 当前的处理。
代码:
const spiralOrder = function (matrix) {
if (matrix.length === 0) return [];
const result = [],
dx = [0, 1, 0, -1],
dy = [1, 0, -1, 0],
col = matrix.length,
row = matrix[0].length;
const isCheckMatrix = Array.from(new Array(col), () => (new Array(row).fill(false)))
const dfs = (x, y, directionIndex) => {
result.push(matrix[x][y]);
isCheckMatrix[x][y] = true
for (let i = 0; i < 3; i++) {
const nextX = x + dx[directionIndex]
const nextY = y + dy[directionIndex]
if (nextX < col && nextX >= 0 && nextY < row && nextY >= 0 && !isCheckMatrix[nextX][nextY]) {
return dfs(nextX, nextY, directionIndex)
}
directionIndex = (directionIndex + 1) % 4;
}
};
dfs(0, 0, 0);
return result
};
后记
后面发现这个是一道leetcode中等的题目，题目链接:
螺旋矩阵: https://leetcode-cn.com/problems/spiral-matrix/
可能写的过程有点简单，最优解应该不是我这个，leetcode评论区里面有很多解法，类似于脑筋急转弯，感兴趣的话可以看看。
最后
对于深度优先遍历算法入门的文章，可以看看我这篇文章:
或者可以阅读原文，掘金阅读体验可能更加友好。
面试交流群持续开放，分享了 许多 个面经。
加我微信: DayDay2021，备注面试，拉你进群。
我是 TianTian，我们下篇见~
