ジャンプゲーム

LeetCode - Jump Game (2021. 08. 29)

質問と回答アドレス

LeetCode
Git Solution

質問の説明-英語

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.
Return true if you can reach the last index, or false otherwise.

問題の説明-翻訳

整数配列numsを指定します.最初は配列の最初のインデックスにあり、配列の各要素はその位置の最大ジャンプ長を表します.
trueの最後のインデックスに到達できる場合は戻り、そうでない場合はfalseを返します.
例1:
Input: nums = [2,3,1,1,4]
Output: true
展開:索引0から索引1に、最後の索引に移動します.
例2:
Input: nums = [3,2,1,0,4]
Output: false
Explanation:何があっても、常にインデックス3に到達します.最大ジャンプ長は0で、最後のインデックスに到達できません.
せいげんじょうけん
1 <= nums.length <= 104
0 <= nums[i] <= 105

トラブルシューティング

ターゲット配列インデックスではすべてのナビゲーションが必要であるため,bfsまたはdfsが必要であると考えられる.でもだんだん山の上へ.コミュニティメンバーの山堂の説明を真剣に聞いて、本当に、一気に解決しました.
重要な部分は以下の通りです.

アクセス方法はi+nums[i]です。

次のインデックス値を取得するには、현재 위치 인덱스값 + 해당 위치 인덱스의 Value값を使用します.

その値段を探さなければならない必要はありません。

各インデックスにループに値がない場合は、--を実行する必要があります.そのため、bfsまたは再帰的な検索を迂回する必要がありますが、そうする必要はありません.各loopのi+nums[i]の値が最大値であり、その最大値(変更するたびに最大値)がその瞬間のi値(位置値)に達するかどうかを決定するだけでよい.

≪イベント｜Events｜ldap≫

bfsを使用してナビゲートするには、このセクションの値が0の場合、ステップ値処理が必要であり、複数のdepressを処理している間に0が持続している場合は、再度--再帰処理が必要であるが、depressが多すぎると処理できない.

完全なコード

爆弾の位置値を探す方法

    public boolean canJump(int[] nums) {
        // nums가 한글자인 경우 0이든 0초과이든 무조건 true
        if(nums.length == 1){
            return true;
        }

        int maxIdx = Integer.MIN_VALUE;        // 인덱스당 최대값 설정
        int lastIdx = nums.length - 1;         // 목표 인덱스 값 설정
        for(int i = 0; i < nums.length; i++){
            maxIdx = Math.max(maxIdx, i + nums[i]); // idx + nums[idx]가 점프해야하는 위치값
            if(maxIdx <= i){    // maxIdx의 값이 대상 위치 인덱스보다 작을 경우 더이상 진행이 불가능하다.
                return false;
            }else if(maxIdx >= lastIdx) {   // maxIdx의 값이 루프가 돌기전에 이미 마지막 값을 넘겼다면 통과
                return true;
            }
        }
        return false;
    }

テスト結果

ポスト

果たしてこのアルゴリズム的なアイデアはどうすれば良いのか、という問題は、レベルが低くても、この方式を知らなければ大量のタックルをするか(でも私はうまくできないので失敗するでしょう)、タイムアウトするか…
後で...やればやるほど難しいアルゴリズム