いいものをつくろう

CTOの日記

アルゴリズム

【アルゴリズム脳トレ】leetcode medium 55 jump game

投稿日:

こんにちは

今回の学びは

アイデアタイマーセット5分ヨーイドンといメリハリ

LTE(Time Limit Exceeded)はtime complexityの大きなヒントである

連続という特性をうまく利用

連続という特性は位置変数で表現できる

アイデアに見切りをつけるための条件を考える

 

問題は。。。

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

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

[3, 2, 11, 7, 4]

*

 

最初のポジションから、最大その数、右に移動できて

それをくりかえして最後のindexにたどり着くことができるか?

 

という問題

 

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

 

最初のポジションで選択してはS[0]つまり最大S[0]の配列の積という膨大な選択肢になることわかる

なので ブルートフォースはダメだなと思う

 

ホワイトボードをつかって

サンプルをあーだこーだしました。

dpっぽことができるんですよ。

ループしてそのS[i]の数分、右のdp[i+x]にTrueいれていく

最終的に最後のdp[-1]がTrueだったokというふうにします。

 

pseudocode(擬似コード)をかいてみますか。

 

dp初期化
for i in range(len(S)):
  for n in range(1, S[i]+1):
    dp[i+n] += 1
return True if dp[i] > 0 else False

 

実際の実装はこちら

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        length = len(nums)
        if length <= 0: return False
        if length == 1: return True
        dp = [0] * length
        dp[0] = 1
        def dp_print():
            for row in dp:
                logging.debug(row)
        def dp_valid(i):
            if i < 0 or i >= length: return False
            else: return True
        def dp_get(i, default=0):
            if dp_valid(i): return dp[i]
            else: return default

        for i in range(length):
            if dp[i] > 0:
                for n in range(nums[i]):
                    if dp_valid(i+n+1):
                        dp[i+n+1] += 1

        return True if dp[i] > 0 else False

いつもの感じで解けたかとおもいきや

TLE

。。。

おー、そうか

こちらの濃厚なテストケースなのね。

O(n * S[i])なのでだめなのね。

なにか他に思いつくアイデアはないか。

模索しましょう

タイマーセット5分ヨーイ、どん!

10分くらいで一個おもいついきましたのでが、こちら。題して

「どこまでいけるかチケット更新リレー!」

どんどんぱふぱふ

これはジャンプできるのが与えられた数字だけではなく、その数字以下なら

いくらでも飛べるということは

どこのindexまでは行けるんだという情報と考えられます。

これは、すばらし発想で

これまでは、例えばnums[3] = 7だったとしたら、次の7つの配列にジャンプできるのでそれぞれのdp[4, 5, ... ,10]にTrueなりをセットしてきました、

この情報って

index 10までジャンプできます

という、一言でいいあらわせます。

これはジャンプできるのが次の連続するxステップという特性を利用しているということです。別の言い方をすると

連続という特性をうまく利用しています

ジャンプでいるのは、次の連続するxステップ、というようなことが

わかったら是非、連続という特性を利用できないか考えてみてください

傾けると、次のように覚えてもいいでしょう。

連続という特性は位置変数で表現できる

 

そうすると、これまではすべてのindexにTrueを代入してきたコストが

この最高ジャンプ到達地点のindexの伝搬して更新するだけでよくなります。

行けそうなきがします。

 

あと、もうひとつアイデアの発想のおいて重要なポイントがあったので言っておきます。

この問題を、どうやってとくか考えるプロセスで、

一番最後のindexに来れればいいのだから、逆算で、最後のindexに来るためには、どのindexにいる必要があるか?と考えます。逆算は柔軟でとてもいい考えかたです。しかし、この問題の場合、どこのindexにいる必要があるかとう、とう問いにたいする答えは、別にどのindexからでも最後までと立つできる可能性はある、とうものでパターン数が多すぎて、役に立たないことがわかります。ですので、この時点で逆算という着想を捨てることができます。

すると前から情報を伝播する、というような方向性に絞り込むことができ。

正解のアルゴリズムの着想までのスピードがあがったはずです。なので

このしっかり方向性やとあるアイデアに見切りをつけられるか、はとても重要で今回のように見切りをつけるための項目を見つけ出し、満たしていなければ切り捨てるというテクニックは、とても大事です。

ということで

アイデアに見切りをつけるための条件を考える

というのも今回の学びにいれておきます

 

実装します

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        length = len(nums)
        if length <= 0: return False
        if length == 1: return True
        dp = [0] * length
        def dp_valid(i):
            if i < 0 or i >= length: return False
            else: return True

        carryover_idx = 0
        for i in range(length):
            x = nums[i]
            possible_best_jumping_idx = i + x
            if dp[i] < i: return False
            carryover_idx = max(possible_best_jumping_idx, carryover_idx)
            if dp_valid(i+1):
                dp[i+1] = carryover_idx

        return True

見事クリアです

 

 

ということで

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

最初の通らなかったtime complexityは O(n * nums[i])で

通ったtime complexityは O(n)でした

 

今回は、LTE出て苦戦しましたが

そこから自力でアイデア発想から実装までもっていけたのは良かった点です。

試しにアイデアタイマーセット5分ヨーイドンといメリハリはよかったとおもいます。全くそこでアイデアが出てこなければヒントや回答を見るつもりでした。

着想自体もサンプルを見返すということと

現在のtimecomplexityで通らなかったのだから

というのは実はたいへん大きなヒントで、

ヒントでO(n * nums[i])では通りません

と書かれていたら、誰でも、頭をひねり出す、他にもっとよいアルゴリズム、工夫があるはずだと!と考え出します。

なので、その情報を自分であぶり出せばよい

つまり、今回、最初にやったアルゴリズムのtime complexityをしっかり分析できていれば O(n * nums[i])ということが分り、

なんとか、O(n)に持っていけないかと考えられるのです。

こうかんがえると、最初のLTEはヒントをあぶり出すための1手で

大変有効だし、全然無駄ではなく必要でかつ、むしろ無駄のない1手だったと思います。time complexityがO(n * nums[i])ではダメという大きなヒントはアイデア着想の手がかりということ

を身を持って感じました。

LTE(Time Limit Exceeded)はtime complexityの大きなヒントである

もちろん

time complexityを分析する能力が重要である

といことの理由の一つだなー、と感じることができたかとおもいます。

 

 

まとめ

アイデアタイマーセット5分ヨーイドンといメリハリ

LTE(Time Limit Exceeded)はtime complexityの大きなヒントである

連続という特性をうまく利用

連続という特性は位置変数で表現できる

アイデアに見切りをつけるための条件を考える

 

以上です

 

 

 

ちなみにこの最後の回答、削ぐとdpはいらないことがわかります。

しかしアイデア的には前の状態を引き継ぐなんかは一種のdpとかんがえてもいいかしれません。

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        length = len(nums)
        if length <= 0: return False
        if length == 1: return True

        carryover_idx = 0
        for i in range(length):
            if carryover_idx < i: return False
            carryover_idx = max(i + nums[i], carryover_idx)
        return True

 

以上です。

-アルゴリズム

Copyright© CTOの日記 , 2020 All Rights Reserved.