こんにちは
今回の学びは
・方向の情報はtupleで方向差分を保持するのがスマート
問題は。。。
（時間配分は5分問題理解 10分検討 10分実装 20分振り返り の一文45分構成)
まずは入出力をしっかりおさえましょう。
これ以外に難しですよねー
パッと思いつくのはvisittedみたいなmatrix用意して、すでに訪れた場所には行かずに、
さらに方向を記憶して右下左上の順番に循環していく方法。
今回はこれで実装しました
というもの、以前この問題か似た問題を解いた時にout of indexを壁みたいに捉えて、m * nの一回り大きくした(m+1) * (n+1)を
こしらえて、壁は-1で表現しようみたいにすると
実は実装が難しく、すごく苦労するか断念することになります。ので、最初のシンプルな考えで実装していきます
実装前後でこれは毎回書きましょう。timespace analysis (時間とスペースの分析）は O(N) with space O(N) for visitted
といったところです
実装の途中で 方向の情報はtupleで方向差分を保持するのがスマート
ということに気づきました
# 方向を以下のようなtupleで表現
direction_set = ((0, 1), (1, 0), (0, -1), (-1, 0))
def change_direction(direction):
direction += 1
if direction == 4:
direction = 0
return direction
# そしてこうして使う
arrow = direction_set[direction]
実際の実装はこちら
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
if len(matrix) == 0: return matrix
if len(matrix[0]) == 0: return []
m = len(matrix)
n = len(matrix[0])
visitted = [[0] * n for _ in range(m)]
# right, down , left , up
direction_set = ((0, 1), (1, 0), (0, -1), (-1, 0))
def change_direction(direction):
direction += 1
if direction == 4:
direction = 0
return direction
def get_next(i, j, direction):
arrow = direction_set[direction]
i_ = i + arrow[0]
j_ = j + arrow[1]
if i_ < 0 or j_ < 0 or i_ >= m or j_ >= n or visitted[i_][j_] == 1:
direction = change_direction(direction)
arrow = direction_set[direction]
i_ = i + arrow[0]
j_ = j + arrow[1]
if i_ < 0 or j_ < 0 or i_ >= m or j_ >= n or visitted[i_][j_] == 1:
return (None, i_, j_, direction) # end
else:
visitted[i_][j_] = 1
return (matrix[i_][j_], i_, j_, direction)
else:
visitted[i_][j_] = 1
return (matrix[i_][j_], i_, j_, direction)
path = []
i = 0
j = -1
direction = 0
for _ in range(m*n):
(value, i, j, direction) = get_next(i, j, direction)
if value == None: break
path.append(value)
return path
実装後です。timespace analysis (時間とスペースの分析）は O(n) with space O(N)
実装は長いですが動きます。
他の人の解答も参考にしておきましょう。
。。。
まとめ
・方向の情報はtupleで方向差分を保持するのがスマート
以上です