Time Limit Exceededです。whileの中で線形探索を毎回おこなっているのが、おそらくの原因です。
#問題
非負整数の配列numsが与えられています。あなたは、開始時には配列の最初のインデックスにいます。
配列の各要素は、その位置から最大で跳べる幅を表しています。
あなたの目標は、最小の跳んだ回数で、最後のインデックスにたどり着くことです。
常に最後のインデックスにたどり着くと仮定して大丈夫です。
問題は、ここから挑戦できます。
https://leetcode.com/problems/jump-game-ii/
#方針
今いるインデックスから次に行くインデックスへ跳んだ回数は、グラフ理論いうところの距離として表現できます。
スタート地点から、グラフ内の全地点の最短の距離を求めるアルゴリズムとして、Dijkstra's algorithmがあります。
Dijkstra's algorithmは、負の値の距離があると使うことができません。今回は、跳んだ回数という正の値しかとらない数字を距離として使うので、Dijkstra's algorithmを使えます。
ダイクストラのアリゴリズムについては、私は『予備校のノリで学ぶ「大学の数学・物理」』で学びました。
グラフ理論⑤(ダイクストラのアルゴリズム)： https://www.youtube.com/watch?v=X1AsMlJdiok
動画の黒板にはこう書いていあります。
1 始点に0を書き込む
2 未確定の地点の中から最も小さい値をもつ地点を1つ選び、その値を確定させる（ルート記憶）
3 2で確定した地点から直接つながっていて、かつ未確定な地点に対し、かかる時間を計算し、画期込まれている数より小さければ更新する
4 全ての地点が確定していれば終了、そうでなければ2に戻る
今回は、すべての地点の最短距離を求める必要はありません。一番最後のインデックスへの最短距離が、欲しい値です。一番最後のインデックスへの最短距離が求まったら、そこで値を返して終了するようにしましょう。
そのため、今回はこのようにします。
1 始点に0を書き込む
2 未確定の地点の中から最も小さい値をもつ地点を1つ選び、その値を確定させる（ルート記憶）。ただし、複数の地点が最小だった場合、最も配列の終わりに近い地点を選ぶ
3 2で確定した地点から直接つながっていて、かつ未確定な地点に対し、かかる時間を計算し、画期込まれている数より小さければ更新する
4 一番最後のインデックスが確定していれば終了、そうでなければ2に戻る
#コード
import copy
class Solution:
def jump(self, nums: List[int]) -> int:
# len(nums)は何度も使いそうなので、予めもらっちゃう。
len_nums = len(nums)
default_dict = {'distance': float('inf'), 'is_ditermined': False}
# ノードを作る。
nodes = [copy.deepcopy(default_dict) for _ in range(len_nums)]
#1 始点に0を書き込む
nodes[0]['distance'] = 0
# 4 一番最後のインデックスが確定していれば終了、そうでなければ2に戻る
while not nodes[-1]['is_ditermined']:
# 2 未確定の地点の中から最も小さい値をもつ地点を1つ選び、その値を確定させる（ルート記憶）。
# ただし、複数の地点が最小だった場合、最も配列の終わりに近い地点を選ぶ
# 線形探索を行うために、候補の場所を記録する辞書(cur_min)を作る。
cur_min = {'index': len_nums, 'value': float('inf')}
for i, node in enumerate(nodes):
node_distance = node['distance']
if not node['is_ditermined']\
and node_distance <= cur_min['value']\
and node_distance != float('inf') :
cur_min['index'] = i
cur_min['value'] = node_distance
# cur_minで示されるnodeを確定させる。
# 線形探索は、配列の左端から右端へと行われているので、
# 「ただし、複数の地点が最小だった場合、最も配列の終わりに近い地点を選ぶ」は達成されている。
#何回もcur_min[index]を書くのが面倒なので、curに省略する。
cur = cur_min['index']
nodes[cur]['is_ditermined'] = True
# cur_min[index]から跳べる場所全てについて考える。
for i in range(nums[cur] + 1):
# 3 2で確定した地点から直接つながっていて、かつ未確定な地点に対し、
if not nodes[min([len_nums -1, cur + i])]['is_ditermined'] :
# かかる時間を計算し、書き込まれている数より小さければ更新する
# 跳びすぎてnumsのrangeを突き抜けないように、minで押さえつける。
nodes[min([len_nums -1, cur + i])]['distance']= min([nodes[min([len_nums -1, cur + i])]['distance'], cur_min['value'] + 1])
return nodes[-1]['distance']
結果：Time Limit Exceeded
#反省
おそらく、whileの中で線形探索を毎回おこなっているのが、Time Limit Exceededの原因だと思います。
ただ、もう午前2時なので、これを解決するには遅すぎます。
続きは、また次回に！
ストゼロ飲んで寝ます！
#追記：結局、どうすれば解けるのか
https://leetcode.com/problems/jump-game-ii/discuss/170518/8-Lines-in-Python!-Easiest-Solution!
ここで提供されている解答がとてもシンプルです。
class Solution:
def jump(self, nums: List[int]) -> int:
# numsの長さが1以下の時には、0を返す。
if len(nums) <= 1:
return 0
# ポインターを2つ用意する。
# lの初期値は0。
# rの初期値は、lの初期値から跳べる最大の場所。
l = 0
r = nums[0]
# ここまでアルゴリズムが来ているということは、1回の跳躍は確定している。
times = 1
# ポインターrが、numsの端を
end = len(nums) - 1
while r < end:
#跳躍回数を1回加算する
times += 1
# 今回の跳躍では、rまでは到達できることが保証されている。
# そのため、rの値を次のステップのlにすることができる。
# 今回の跳躍で、現在のrを越えるもののうちの最大値を、
# 次のステップのrにする。
# l番目からr番目までにある各iについて、
# i番目から、nums[i]だけ跳んだものの最大値を、次のステップのrにする。
next_r = max(i + nums[i] for i in range(l, r + 1))
l = r
r = next_r
return times
こんなの、思いつかねーぜ！