Jump Game
配列 nums のインデックス 0 にいます。インデックス i からは、1 から nums[i] までの任意の歩数だけ前方にジャンプできます。つまり、nums[i] はそこからの最大ジャンプ距離であり、0 の場合は移動できません。何らかのジャンプ列で最後のインデックスに到達できる場合は true を、そうでない場合は false を返してください。
関数
- numsinteger-array
- 各インデックスから跳べる最長距離
- 戻り値boolean
- インデックス 0 から始めて最後のインデックスに到達できる場合は true、それ以外の場合は false
制約
1 ≤ nums.length ≤ 1040 ≤ nums[i] ≤ 105- ジャンプの長さは
nums[i]より短いことがあるため、長いジャンプでも最後のインデックスを飛び越えることはありません。
例
- 入力
- nums = [2, 0, 3, 1, 0, 2]
- 出力
- true
- 説明
- インデックス 0 からはインデックス 1 または 2 に進めます。インデックス 1 には 0 が格納されており行き止まりですが、インデックス 2 には 3 が格納されており、最後のインデックスであるインデックス 5 に到達できます。
- 入力
- nums = [1, 3, 0, 0, 0, 2]
- 出力
- false
- 説明
- インデックス 0 から進めるのはインデックス 1 だけで、インデックス 1 から到達できるのは最大でもインデックス 4 です。インデックス 2、3、4 はすべて 0 なので、インデックス 4 を越えてインデックス 5 に到達することはありません。
- 入力
- nums = [0]
- 出力
- true
- 説明
- 配列には要素が1つあるため、最後のインデックスから開始し、ジャンプはまったく必要ありません。
提出時に隠しテスト+18件
発展問題
最後のインデックスに到達する異なるジャンプ列の数を、10^9+7 を法として、引き続き O(n) 時間で求めます。
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
0があなたを罠にはめるのは、それより前にあるどの要素も飛び越えられないときだけです。それを判断するには、手前のインデックスについて何を知る必要がありますか？インデックス
iに到達できるなら、より短いジャンプも可能なので、iからi+nums[i]までのすべてのインデックスに到達できます。したがって、到達可能なインデックスは常に、インデックス 0 から始まる途切れのないひと続きのブロックになります。左から右へ進み、そのブロックの右端である
farthestを保持します。現在のインデックスがfarthestを超えている場合、そこには決して到達できません。それ以外の場合は、i+nums[i]のほうが大きければ、farthestをそこまで伸ばします。配列全体を最後まで進めた場合、最後のインデックスに到達できます。
解説
可能な経路の数は指数関数的に増加するため、長い配列では経路を1つずつ確認する方法は使えません。重要なのは、到達できるインデックスは常にインデックス0から始まる途切れのない区間を形成するという事実です。その区間の右端を表す1つの数に必要な情報がすべて含まれており、1回走査するだけで答えを判断できます。
すべてのジャンプを試す
正しいが、最大のテストでは終わらない
考え方
最も直接的な方法は、実際にたどってみることです。インデックス 0 に立ち、ジャンプで行けるすべての着地点を1つずつ試します。それぞれの着地点から、同じことを繰り返します。どれかの分岐が最後のインデックスにたどり着けば、答えは true です。すべての分岐が行き止まりにぶつかれば、false です。
最初の例では、インデックス 0 の値は 2 なので、インデックス 1 とインデックス 2 を試します。インデックス 1 の値は 0 で行き止まりなので、戻ってインデックス 2 を試します。インデックス 2 の値は 3 で、最後のインデックスであるインデックス 5 に到達するため、探索は true で終了します。
この探索が正しいのは、あらゆる経路を調べるからです。それが同時に問題でもあります。すでに調べたインデックスを記憶しないため、そのインデックスにたどり着く経路ごとに同じインデックスを再び調べます。答えが false の場合、あらゆる経路を排除しなければなりません。[4, 3, 2, 1, 0, 5] では、0より前の各インデックスから0に到達できるため、0に至る経路は8通りあります。このようなインデックスが30個あると経路は5億通りを超え、最大のテストでは要素数が10,000です。また、これほど長い経路では、一部の言語でコールスタックがオーバーフローします。Pythonでは、デフォルトで1,000回のネストした呼び出しで停止します。
アルゴリズム
- インデックス
iから最後のインデックスに到達できるかを判定するヘルパーreach(i)を書きます。 iが最後のインデックスなら、trueを返します。- それ以外の場合は、
i+1からmin(i+nums[i], n-1)までのすべての着地点nextを試し、reach(next)がtrueを返したらすぐにtrueを返します。 - どの着地点でも到達できない場合は、
falseを返します。 - 答えは
reach(0)です。
def canJump(nums):
last = len(nums) - 1
def reach(i):
# Can you get from index i to the last index?
if i == last:
return True
for nxt in range(i + 1, min(i + nums[i], last) + 1):
if reach(nxt):
return True
return False
return reach(0)どのインデックスで終了できるかを覚えておきましょう
正しいが、最大のテストでは終わらない
考え方
上の検索では、「インデックス j からゴールできるか？」という同じ質問を何度も繰り返しています。j についての答えは変わらないので、一度だけ計算して保存しましょう。そこから最後のインデックスに到達できるとき、そのインデックスを良好と呼びます。最後のインデックスは良好です。それ以外のインデックス i は、i+1 から i+nums[i] までの、そこから到達できるインデックスのうち少なくとも1つが良好なら、良好です。
各インデックスは右側のインデックスだけに依存するので、テーブル good を右から左へ埋めていきます。最初の例では、インデックス5は良好です。インデックス4の値は0なので、良好ではありません。インデックス3から到達できるのはインデックス4だけなので、良好ではありません。インデックス2からはインデックス3、4、5に到達でき、5は良好なので、2も良好です。インデックス1の値は0なので、良好ではありません。インデックス0からは1と2に到達でき、2は良好なので、答えは true です。
これで各インデックスは一度だけ判定されますが、判定の際に最大で n 個の要素を調べることがあります。[9998, 9997, …, 1, 0, 7] では、どのインデックスからも0には到達できますが、その先には到達できません。そのため、各インデックスで範囲全体を調べても、良好なインデックスは見つかりません。要素数が10,000の場合、チェック回数は約5 × 10^7回になり、最大規模のテストケースはこの例のように作られています。処理量は長さの2乗に比例して増えるため、これらのテストケースでは時間切れになります。
アルゴリズム
- 長さが
nのブール配列goodを作成し、good[n-1]を true に設定します。 iをn-2から 0 まで逆順に確認します。jをi+1からmin(i+nums[i], n-1)まで調べます。good[j]のいずれかが true なら、good[i]を true に設定し、走査を終了します。good[0]を返します。
def canJump(nums):
n = len(nums)
good = [False] * n # good[i]: from i you can reach the last index
good[n - 1] = True
for i in range(n - 2, -1, -1):
for j in range(i + 1, min(i + nums[i], n - 1) + 1):
if good[j]:
good[i] = True
break
return good[0]到達可能な最遠のインデックスを追跡する
考え方
経路ではなく、到達できるインデックスに注目してください。インデックス i からは、間を飛ばさずに i+1 から i+nums[i] までの任意のインデックスに着地できます。したがって、インデックス i に到達できるなら、i+nums[i] までのすべてのインデックスにも到達できます。最初はインデックス 0 だけを対象とし、こうした範囲を追加していきます。新しい範囲は常にすでに到達できるブロックの内側から始まるため、到達可能なインデックスは常に途切れのない1つのブロック、[0, farthest] を形成します。
そのため、数値を1つだけ管理すれば十分です。i を左から右へ進めます。i ≤ farthest の間はインデックス i に到達できるので、farthest を max(farthest, i+nums[i]) まで伸ばします。もし i が farthest を超えたら、到達可能なインデックスから i へジャンプすることはできません。ブロックはその隙間を越えて広がれないため、その右側にあるインデックスには、最後のインデックスも含めて到達できません。隙間に遭遇せず最後まで進めば、最後のインデックスに到達できます。
2つ目の例では、farthest は 0 から始まり、インデックス 0 の後に 1、インデックス 1 の後に 4 になります。インデックス 2、3、4 は 0 なので、farthest は 4 のままです。インデックス 5 は 4 を超えているため、答えは false です。1つ目の例では、インデックス 2 によって farthest が 5 まで伸び、それを超えるインデックスはないため、答えは true です。
最大の到達範囲だけを保持しても問題ないのはなぜでしょうか？ジャンプ先を1つに決めているわけではありません。このブロックには、どの経路からでも到達できるすべてのインデックスが含まれており、より手前の着地点もすべてその内側にあります。右端以外を捨てても、情報は失われません。
アルゴリズム
farthest = 0を設定します。- 左から右へ各インデックス
iについて、i > farthestの場合はfalseを返します。 - そうでなければ、
farthest = max(farthest, i+nums[i])を設定します。 - ループが終了した場合、すべてのインデックスに到達できたので、
trueを返します。
def canJump(nums):
farthest = 0 # every index up to farthest can be reached
for i, jump in enumerate(nums):
if i > farthest:
return False # nothing reachable jumps to i
farthest = max(farthest, i + jump)
return True
落とし穴と境界ケース
誤答の多くは、nums[i]を唯一のジャンプだと読み違えたり、ループ内の2つのチェックの順序を間違えたりすることが原因です。
- 常にちょうど
nums[i]歩ジャンプする、または常に最長のジャンプをする。[2, 5, 0, 0]では、インデックス0からの全距離のジャンプは0に着地しますが、インデックス1への1歩のジャンプなら末尾に到達できます。 - 0を見つけたらすぐに
falseを返す。0が問題になるのは、それより前の位置から0を飛び越えられない場合だけです。[2, 0, 1]では0を飛び越えるので、答えはtrueです。 i > farthestをチェックする前にfarthestを更新する。到達できないインデックスでブロックを広げてはいけないので、先にチェックしてから更新します。- 要素が1つの配列を失敗とみなす。すでに最後のインデックスにいるため、その要素が0でも答えは
trueです。 - 長い配列で再帰を使う。経路が10,000回のジャンプに及ぶこともあり、いくつかの言語ではコールスタックがオーバーフローします。1回の走査では再帰を使いません。
よくある質問4
Jump Game の時間計算量は何ですか？
最も遠くまで到達するパスでは各インデックスを1回ずつ訪問するため、時間計算量は O(n)、追加の空間計算量は O(1) です。テーブルを使う方法は最悪の場合 O(n²) で、すべての経路を試すと指数時間になります。
Jump Game で貪欲法がうまくいくのはなぜですか？
より短いジャンプも可能なため、インデックス i に到達できれば、i+nums[i] までのすべてのインデックスに到達できます。こうした範囲は、すでに到達した部分と常に重なるため、到達可能なインデックスは 0 から始まるひと続きのブロックになります。貪欲法の走査では、そのブロック全体を表す右端だけを追跡するため、うまくいく可能性のある経路を決して見落としません。
Jump Gameは動的計画法の問題ですか？
動的計画法で解くことができます。右から左へ表を埋めながら、着地点のいずれかが到達可能なインデックスであれば、そのインデックスも到達可能として印を付けます。計算量は O(n²) です。到達可能なインデックスのうち最も左にあるものだけが重要です。あるインデックスから到達可能なインデックスに進めるなら、最も左のインデックスにも進めるからです。そのインデックス goal だけを保持し、i+nums[i] ≥ goal のときは i に更新します。答えは goal が最終的に 0 になるかどうかです。これは貪欲法と同様に、O(n) の一度の走査で求められます。
最小ジャンプ数はどのように求めますか？
同じ最遠到達点の考え方を、層に分けて使います。現在のジャンプ回数で到達できるブロックの末尾と、次のジャンプで到達できる最遠のインデックスを保持します。iが現在のブロックの末尾を越えたら、ジャンプがもう1回必要になり、次のブロックの末尾はその最遠インデックスになります。これも依然として1回のO(n)の走査です。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def canJump(nums):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
nums = [2, 0, 3, 1, 0, 2]
期待値
true