【アルゴリズム脳トレ】leetcode medium 54 spiral matrix

投稿日：2019年9月24日

こんにちは

今回の学びは

・方向の情報は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)

実装は長いですが動きます。