https://leetcode.com/problems/spiral-matrix-iii
※ 引述《involution ( )》之銘言：
: 885. Spiral Matrix III
: 無聊的模擬題 只是想分享一下繞圈圈的四個方向有幾種寫法
: 1.
: direction = [[0, 1], [1, 0], [0, -1], [-1, 0]]
: 非常標準的寫法，分別寫出四個方向的xy移動量
: 2.
: dx = [0, 1, 0, -1]
: dy = [1, 0, -1, 0]
: 跟上面就是 AoS/SoA 的差別，也很常見
: 3.
: direction = [0, 1, 0, -1, 0]
: 觀察之後會發現 [direction[i:i+2] for i in range(4)]
: 剛好就和第一種寫法是一樣的結果
: 是一個有趣但如果有其他人要看你code就不適合的寫法
: 4.
: dx, dy = dy, -dx
: 我覺得也是巧合，不過硬要解釋說這就是順時針旋轉也解釋的通（外積之類的）
: 反正如果需要跟人解釋的話我不會這麼寫
: :)
給一個起始點 (rStart, cStart) 跟網格 rows x cols
面向東順時針走 超出網格範圍也會繼續行走 直到網格的所有空間都走過一遍
根據碰到的網格順序 回傳座標數組
Example 1:
https://s3-lc-upload.s3.amazonaws.com/uploads/2018/08/24/example_1.png
Input: rows = 1, cols = 4, rStart = 0, cStart = 0
Output: [[0,0],[0,1],[0,2],[0,3]]
Example 2:
https://s3-lc-upload.s3.amazonaws.com/uploads/2018/08/24/example_2.png
Input: rows = 5, cols = 6, rStart = 1, cStart = 4
Output: [[1,4],[1,5],[2,5],[2,4],[2,3],[1,3],
[0,3],[0,4],[0,5],[3,5],[3,4],[3,3],
[3,2],[2,2],[1,2],[0,2],[4,5],[4,4],
[4,3],[4,2],[4,1],[3,1],[2,1],[1,1],
[0,1],[4,0],[3,0],[2,0],[1,0],[0,0]]
思路：走法分4種 steps = [[0, 1], [1, 0], [0, -1], [-1, 0]]
可以發現每種走法的次數是 1, 1, 2, 2, 3, 3, 4, 4, ...
所以每2個走法 走的次數要 +1
最後循環直到答案數量滿足 rows * cols
Python Code:
class Solution:
def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int)
-> List[List[int]]:
step = 1
st = 0
steps = [[0, 1], [1, 0], [0, -1], [-1, 0]]
answer = [[rStart, cStart]]
total = rows * cols - 1
while total:
for i in range(step):
rStart += steps[st % 4][0]
cStart += steps[st % 4][1]
if 0 <= rStart < rows and 0 <= cStart < cols:
answer.append([rStart, cStart])
total -= 1
if not total:
return answer
if st % 2:
step += 1
st += 1
return answer
https://i.imgur.com/J69Filp.png