一道字節(jié)筆試題，沒有想到考察的是....
點(diǎn)擊上方關(guān)注 TianTianUp，一起學(xué)習(xí)，天天進(jìn)步
大家好，我是TianTian。
分享的內(nèi)容是字節(jié)的筆試題，字節(jié)的算法題。
考察的點(diǎn)，可以歸納于深度優(yōu)先遍歷，或者說是一道腦筋急轉(zhuǎn)彎題。
題目
給定一個(gè)包含 m x n 個(gè)元素的矩陣（m 行, n 列），請按照順時(shí)針螺旋順序，返回矩陣中的所有元素。
輸入：
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
輸出:
[1,2,3,6,9,8,7,4,5]
思路
基本上圍繞的思路就是:一層層向里處理，按順時(shí)針依次遍歷：上、右、下、左。
其實(shí)很類似于迷宮的走法，走到格子后，判斷下一個(gè)格子，還能不能走，也就是邊界條件。遇到邊界條件后，順著上面的順序: 上、右、下、左。
所以我們可以有幾個(gè)約束條件:
是不是在這個(gè)范圍內(nèi)，不能超過這些范圍。 這個(gè)格子是不是走過，存一下之前的狀態(tài)。 記錄當(dāng)前方向，抱著下一個(gè)方向是對的。
深度優(yōu)先遍歷
按照深度優(yōu)先遍歷思路來寫，我們可以構(gòu)造常見的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
};
這應(yīng)該就是基礎(chǔ)的模版，唯一不同的是，我們看dfs的三個(gè)參數(shù)，x,y,directionIndex。
x和y參數(shù)很好理解，這個(gè)directionIndex參數(shù)含義就是告訴我們當(dāng)前前進(jìn)的方向。
接下來，是寫我們的邏輯部分。首先確定接下來走到哪一個(gè)格子:
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
const nextX = x + dx[directionIndex]
const nextY = y + dy[directionIndex]
根據(jù)當(dāng)前的格子所在的位置x,y我們就知道接下來要走的位置，通過directionIndex的下標(biāo)索引，知道我們下一個(gè)格子的坐標(biāo)。
然后就是判斷一下，邊界的情況：
不能出界 判斷能不能走
根據(jù)以上的信息，其實(shí)我們主要的邏輯部分就完成啦。
代碼:
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 // 標(biāo)記走過
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)
}
// 方向取余數(shù)
directionIndex = (directionIndex + 1) % 4;
}
};
dfs(0, 0, 0);
return result
};
這里我們需要對方向做余數(shù)處理。在確只有四個(gè)方向的情況，并且在這個(gè)方向不能走的情況下，嘗試下一個(gè)方向。
directionIndex = (directionIndex + 1) % 4;
優(yōu)化
寫完的時(shí)候，我在想能不能優(yōu)化一下，做個(gè)減枝的處理，后面發(fā)現(xiàn)，當(dāng)前這個(gè)位置可以走的話，是不是就不能判斷其他方向了。
或者說我們可以提前走出這個(gè)循環(huán)，這里做的優(yōu)化就是return 當(dāng)前的處理。
代碼:
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
};
后記
后面發(fā)現(xiàn)這個(gè)是一道leetcode中等的題目，題目鏈接:
螺旋矩陣: https://leetcode-cn.com/problems/spiral-matrix/
可能寫的過程有點(diǎn)簡單，最優(yōu)解應(yīng)該不是我這個(gè)，leetcode評論區(qū)里面有很多解法，類似于腦筋急轉(zhuǎn)彎，感興趣的話可以看看。
最后
對于深度優(yōu)先遍歷算法入門的文章，可以看看我這篇文章:
「算法與數(shù)據(jù)結(jié)構(gòu)」DFS和BFS算法之美
或者可以閱讀原文，掘金閱讀體驗(yàn)可能更加友好。
面試交流群持續(xù)開放，分享了 許多 個(gè)面經(jīng)。
加我微信: DayDay2021，備注面試，拉你進(jìn)群。
我是 TianTian，我們下篇見~
