【アルゴリズム脳トレ】第2回　leetcode マラソン　3問

こんにちは

今回の学びは

・bashの正規表現でスペースは[[:space:]]

・bashでファイルをwhileで読んで~=で正規表現くらいは出来てね

マラソンのやりかた

マラソンでは一時間で難問とけるかのトライアルです。今までの練習の実践編です。

できるだけ解ければ良しなのですが、1問解く時間の目安は20分としてみます。

マラソン中は振り返らず、終了後にいつものように「次のこの問題を解くばあい知っていればよい一つの事実とは？」

とう問題の核となるものを抽出していきます。

問題の選び方は、今はleetcodeのpick nextで良さげなもを選ぶ、というほぼノールールでいきます。

それでは始めます。(適当な問題へのリンクはこちら、ここからPick Oneでスタート!)

8:03 start

1問目 => medium 71. Simplify Path

満足のでき。

実装前の考察というか、言葉数、これでいける！といって実装を始めたのではなく、やりながら、見つけたのでそこは反省点。

class Solution:
    def simplifyPath(self, path: str) -> str:
        canonical = []
        for element in path.split('/'):
            if element == '' or element == '.':
                pass
            elif element == "..":
                if len(canonical) > 0:
                    canonical.pop()
            else:
                canonical.append(element)
        return "/" + "/".join(canonical)

次！

easy 189. Rotate Array

easyなのに、私には難しく感じて最初の案にたどり着くまで

15分考えた。そして出てきたのはtmps = []に後ろからk分、保存しておく

というもの。

他にspace O(1)とか思いつかないので、これで実装はじめていいですか？始めます。

一応、クリアできましたね。工夫は入力がk > szになり得るのでその時は、どう扱えばよういかという対応ですね。これがないと通らないですがw 必須な工夫です

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        tmps = []
        sz = len(nums)
        if k > sz:
            k = k % sz
        #print("k:%s, %s %s %s" % (k, sz-1, sz-1-k, -1))
        for i in range(sz-1, sz-1-k, -1):
            tmps.append(nums[i])
        for i in range(sz - k -1, -1, -1):
            #print("%s <- %s" % (i+k, i))
            nums[i+k] = nums[i]
        i = 0
        while len(tmps) > 0:
            x = tmps.pop()
            nums[i] = x
            i += 1

なんとかできたものの

解答を見ておさらいする必要がありそうな問題です。

Python solution faster than 93%, O(1) space 三箇所にわけてレバース！！

理解できてないですので、暇な時にもどってきます。

次の問題としては、rotate listなんかもいいでしょう。

次！easy valid-phone-numbers

まず！bashとかいきなり聞かれた面食らうのでとりあえず

ググりながら取り組む。

while read line
do
    if [[ $line =~ "^\([0-9]{3}\) [0-9]{3} [0-9]{4}$" ]]; then
        echo $line
    elif [[ $line =~ "[0-9]{3} [0-9]{3} [0-9]{4}" ]]; then
        echo $line
    else
        echo "else -> $line"
    fi
done < file.txt

あれ！？最後の行がでない！それは最後の行が改行されてないからで

そんなトリッキーな入力が渡される可能性がある場合は

こう！`while read line`が空行じゃなければループ続行

while read line || [ -n "${line}" ]; do
  echo $line
done < file.txt

・bashでファイルをwhileで読んで~=で正規表現くらいは出来てね

スペースのマッチのしかたがわからない！！以下、意図通り動きません！

while read line || [ -n "${line}" ]
do
    if [[ $line =~ "^\([0-9]{3}\) [0-9]{3} [0-9]{4}$" ]]; then
        echo $line
    elif [[ $line =~ "[0-9]{3} [0-9]{3} [0-9]{4}" ]]; then
        echo $line
    elif [[ $line =~ '[0-9]{3} [0-9]{4}' ]]; then
        echo "dummy -> $line"
    else
        echo "else -> $line"
    fi
done < file.txt

仰々しいですが

スペースは`[[:space:]]`　と表記するようです（how-can-i-match-spaces-with-a-regexp-in-bash）

elif [[ $line =~ [0-9]{3}[[:space:]][0-9]{4} ]]; then

・bashの正規表現でスペースは[[:space:]]

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

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

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

この問題を解いてやって前回の問題153 find-minimum-in-rotated-sorted-array　の意図がわかった。

バイナリーサーチの検索はO(logN)だよ、O(N)よりはえーぞ、と。

1問目 => medium 71. Simplify Path => linuxのパスでcanonicalっていうのがあります。

次！easy valid-phone-numbers => while read lineを覚えておきましょう

easy 189. Rotate Array => 一個づらすのをどうやって解くかかんがえてみましょうか？

まとめ

・bashの正規表現でスペースは[[:space:]]

・bashでファイルをwhileで読んで~=で正規表現くらいは出来てね

以上です

【アルゴリズム脳トレ】第2回 leetcode マラソン 3問

【アルゴリズム脳トレ】第2回　leetcode マラソン　3問