【アルゴリズム脳トレ】leetcode medium 6 zigzag conversion

こんにちは

今回の学びは

・状態を考えれたこと

・[[]] * 3しても参照になっちゃうので注意

・サンプルで試すことでパターンを見出すこと、それを一般化(Nとかxとかの関数や数式化）すること、が目標

問題はzigzag-conversion

（時間配分は5分問題理解　10分検討 10分実装  20分振り返り　の一文45分構成)

まずは入出力をしっかりおさえましょう。

実装前後でこれは毎回書きましょう。timespace analysis (時間とスペースの分析）は　

pseudocode（擬似コード）をかいてみますか。

あの、サンプルで試すことでパターンを見出すこと、それを一般化(Nとかxとかの関数や数式化）すること、が目標

実際の実装はこちら

sys.setrecursionlimit(314159265)
from collections import defaultdict

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        k = numRows
        if numRows <= 1: return s
        dir = 1 #上向き
        idx = [-1] * len(s)
        j = 0
        for i in range(len(s)):
            if dir == 1:
                idx[i] = j
                j += 1
                if j == (k):#下段ヒット
                    dir = -1
                    j  = k-2
            else:
                idx[i] = j
                j -= 1
                if j == -1: #上段hit
                    dir = 1
                    j = 0+1
        #print("idx:%s" % idx)
        mapping = [ [] for _ in range(numRows)]
        #print("mapping:%s" % mapping)
        for i, index in enumerate(idx):
            #print(i, index)
            mapping[index].append(i)
        #print("mapping:%s" % mapping)
        ans = ""
        for indice in mapping:
            for i in indice:
                ans += s[i]
        return ans

実装後です。timespace analysis (時間とスペースの分析）は　O(N)

途中、気になったのは

mapping = [ [] ] * numRows

mapping:[[], [], []]
mapping:[[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13], [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13], [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]]

となってしまって、あれ？と思った。どうやら同じリストを参照さししまっているよだ。
そこで以下の様に変更して意図通りに。

mapping = [ [] for _ in range(numRows)]
mapping:[[], [], []]
mapping:[[0, 4, 8, 12], [1, 3, 5, 7, 9, 11, 13], [2, 6, 10]]

「次のこの問題を解くばあい知っていればよい一つの事実とは？」

上限に移動するだけなんで簡単。行のindexを保存していけばよいだけ。

まとめ

・状態を考えれたこと

・[[]] * 3しても参照になっちゃうので注意

・サンプルで試すことでパターンを見出すこと、それを一般化(Nとかxとかの関数や数式化）すること、が目標

以上です