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 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.251.52.67 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1723087289.A.837.html