算法的重要性，我就不多說了吧，想去大廠，就必須要經過基礎知識和業務邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號後續每天帶大家做一道算法題，題目就從LeetCode上面選 ！
今天和大家聊的問題叫做 螺旋矩陣，我們先來看題面：
https://leetcode-cn.com/problems/spiral-matrix/
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
題意給定一個包含 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]
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
# 定義方向數組
fx = [[0, 1], [1, 0], [0, -1], [-1, 0]]
n = len(matrix)
if n == 0:
return []
m = len(matrix[0])
ret = []
# 定義邊界數組
# 邊界數組和旋轉的順序也是對應的
# 第一次旋轉之後上邊界+1，所以第0位是上邊界
# 第二次旋轉之後，右邊界-1
# 以此類推
condition = [0, m-1, n-1, 0]
x, y, dt = 0, 0, 0
for i in range(n * m):
ret.append(matrix[x][y])
x_, y_ = x + fx[dt][0], y + fx[dt][1]
# 如果已經越過邊界了，則需要轉向
if x_ < condition[0] or x_ > condition[2] or y_ < condition[3] or y_ > condition[1]:
# 更新邊界
if dt in (1, 2):
condition[dt] -= 1
else:
condition[dt] += 1
# 轉向，並且重新移動
dt = (dt + 1) % 4
x_, y_ = x+fx[dt][0], y+fx[dt][1]
# print(x_, y_)
x, y = x_, y_
return ret
我們觀察一下代碼，還有一個我們剛才沒有提到的細節。我們在移動的時候，並不是直接在原變量上進行變更，因為如果一旦移動超界或者觸發其他非法的情況，那麼我們就無法回滾了。所以我們會創建新的x和y的變量來表示移動之後的位置，即使移動到了非法位置，也不會影響之前的結果。這也是一個常用的技巧，在Python當中，我們在變量末尾加上下劃線表示這是一個影子（克隆）變量。總結我個人認為今天的題目出得不錯，初學者很有必要親自動手做一下。因為在做題的過程當中我們可以很具體地學到方向數組這個很有用的解題技巧，它在搜索問題當中廣泛使用，可以說是做算法題必須會的技巧之一。可能你會覺得我們通過邊界判斷是否需要轉向的邏輯看起來有些複雜，這並不是必須的。我們也可以使用一些其他方法來代替，比如我們可以開闢一個數組記錄已經遍歷過的位置來代替邊界的判定，和使用邊界判定的方法相比，這樣做消耗的空間要更大一些，並且通過邊界判定的方法更加考驗思維一些，因此我個人比較推薦。好了，今天的文章就到這裡，如果覺得有所收穫，請順手點個在看或者轉發吧，你們的支持是我最大的動力。