毎週1つのアルゴリズム問題(42)

今週のテーマ難易度レベル「Medium」、言語「C」を使う
タイトル:非負の数からなる集合をあげて、最初のインデックスの数から下に「ジャンプ」して、最後の数まで「ジャンプ」できるかどうかを見ます.eg:[2,3,1,1,4]、最初のインデックスは2なので、最初のインデックスから2ステップ「ジャンプ」し、2番目のインデックス3に「ジャンプ」したときに「3」ステップをジャンプすることができ、明らかにジャンプが完了する.さらにeg:[3,2,1,0,4]、最初のインデックスは3で、最初のインデックスから「ジャンプ」3ステップが始まり、0にジャンプしたとき、前の3,2,1,0はすべてジャンプ済みで、ジャンプできないのでfalseに戻ります.
考え方:ジャンプするか、1つのインデックスが1つのインデックスを歩くか、最初のインデックスが数歩ジャンプできるかどうか、次のインデックスにジャンプするときにジャンプできるステップ数を更新して、最後にジャンプできるかどうかを見ます.難しくないです.コードを見てください.

bool canJump(int* nums, int numsSize) {
    //       ，    true（0  true）
    if (numsSize == 1) return true;
    //        
    int temp = nums[0];
    //          
    int i = 0;
    //       0    
    while (temp != 0) {
        //        true
        if (nums[i] +i >= numsSize - 1) return true;
        //    
        temp--;
        //       
        i++;
        //       
        if (temp < nums[i]) temp = nums[i];  
    }
    return false;
}

効率はまあまあでしょう.whileはforに変えることができます.forは一般的に既知の遍歴回数に使われています.whileは一般的に未知の遍歴回数に使われています.この問題は明らかに最大遍歴回数がnumsSizeを超えないことを知っています.だから、forを使うほうがいいです.私は変えません.またこの問題は「欲張りアルゴリズム」も「欲張りアルゴリズム」と呼ばれ、興味のある仲間は自分で知ることができます.の
本文はCrazy Stevenのオリジナルの出品で、転載を歓迎して、転載する時出典を明記してください!