Pythonで終了位置に到達するために必要な最小ホップ数を見つけるためのプログラム

すべての要素が正である1つの配列numがあるとします。インデックス0にいます。ここで、配列の各要素は、その位置での最大ジャンプ長を表します。私たちの目標は、ジャンプの数を減らして、最終的なインデックス（n-1、nはnumsのサイズ）に到達することです。したがって、配列が[2,3,1,1,4]のようである場合、出力は2になります。これは、0からインデックス1にジャンプしてから、最後のインデックスであるインデックス4にジャンプできるためです。

これを解決するには、次の手順に従います-

• 終了：=0、ジャンプ：=0、最も遠い：=0
• 0からnumsの長さの範囲のiの場合– 1
  • farthest：=farthestとnums[i]+iの最大値
  • iが終了し、iがnums – 1の長さでない場合、
    • ジャンプを1つ増やします
    • end：=最も遠い
• リターンジャンプ

理解を深めるために、次の実装を見てみましょう-

例

class Solution(object):
   def jump(self, nums):
      end = 0
      jumps = 0
      farthest = 0
      for i in range(len(nums)):
         farthest = max(farthest,nums[i]+i)
         if i == end and i != len(nums)-1:
            jumps+=1
            end = farthest
      return jumps
ob = Solution()
print(ob.jump([3, 4, 3, 0, 1]))

入力

[3, 4, 3, 0, 1]

出力

2