非負の整数配列を指定すると、最初に配列の最初の位置に位置します.
配列内の各要素は、その位置でジャンプできる最大長を表します.
あなたの目標は、最小のジャンプ回数を使って配列の最後の位置に到達することです.
例:
入力:[2,3,1,1,4]出力:2解釈:最後の位置にジャンプする最小ジャンプ数は2である.下付き文字が0から下付き文字が1の位置にジャンプし、1ステップジャンプし、3ステップジャンプして配列の最後の位置に着きます.
ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/jump-game-ii著作権はインターネットの所有に帰属する.商業転載は公式の授権に連絡してください.非商業転載は出典を明記してください.
この問題に対して,私は2つの解法を使った.

1.目標位置に到達した直近点を直接探す

現在の位置に対して、現在の位置に対応する値は私たちが到達できる最も遠い値であり、私たちは左から右まで一気に目標値にジャンプできる位置を探すだけで、その位置は私たちの次の目標値であり、例の入力を例に2、3、1、4として、最初はstep=0を設定し、私たちの目標値は4の最後の位置、すなわちtarget=4として、左から右に遍歴し、1番目の位置index=0ではターゲット位置にジャンプできないので、次に見てみると、2番目の位置index=1は一気にターゲット位置にジャンプできるので、step+、ターゲット値target=1を再遍歴し、今回は1番目の位置index=0からターゲット位置に直接ジャンプできるので、step+、そしてtarget=0と、すでに0なので出力します.

var jump = function(nums) {
    let target = nums.length-1;
    let step = 0;
    while(target !=0){
        for(let i=0;i<target ;i++){
            if(nums[i]>=target -i){ //          
                target =i;
                step++;
                break;
            }
        }
    }
    return step;
};

時間複雑度:O(n*n)

2.欲張りアルゴリズム

上記の方法は可能であるが、O(n*n)の時間的複雑さが高すぎるため、欲張りアルゴリズムを用いて現在位置毎に現在位置がジャンプできる位置のうち、どの位置がより遠くまでジャンプできるかを判断し、その位置にジャンプし、ある位置が目標値までジャンプできるまで停止し、例入力を例2、3、1、4 step=0、index=0の位置で、現在ジャンプ可能なのはindex 1=1とindex 2=2の位置であり、index 1の位置がジャンプ可能な最遠距離はindex 1+nums[index 1]=4であり、index 2がジャンプ可能な最遠距離はindex 2+nums[index 2]=3であるため、index 1の位置にジャンプし、step++はindex 1の位置にジャンプし、現在ジャンプ可能な位置は目標位置target=4を超えていると判断したので、遍歴をジャンプし、step+、stepに戻るのは2コードは以下の通りである.

var jump = function(nums) {
    let target = nums.length-1;
    let step = 0;
    let index = 0;
    while(index<target&&index+nums[index]<target){
        let max = index+1; //                 
        let maxI = index+1; //                   
        step++;
        for(let i =1;i<=nums[index];i++){
            if(index+i+nums[index+i]>max){ //            
                max=index+i+nums[index+i];
                maxI=index+i;
            }
        }
        index = maxI;
    }
    if(index<target)
        step++;
    return step;
};

貪欲アルゴリズムを用いた時間複雑度O(n)