HomeAboutMeBlogGuest
© 2025 Sejin Cha. All rights reserved.
Built with Next.js, deployed on Vercel
👻
개발 기록/
코딩테스트 스터디
코딩테스트 스터디/
Jump Game II

Jump Game II

Link
https://leetcode.com/problems/jump-game-ii/
Deadline
Mar 28, 2023
Status
Archived
Type
Array
DP
greedy

문제

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].
Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:
  • 0 <= j <= nums[i] and
  • i + j < n
Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].
Example 1:
Example 2:
Constraints:
  • 1 <= nums.length <= 104
  • 0 <= nums[i] <= 1000
  • It's guaranteed that you can reach nums[n - 1].

풀이

효성
재영
은찬
 
Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Input: nums = [2,3,0,1,4]
Output: 2

var jump = function (nums) {
    const len = nums.length;
    let answer = 0;
    let idx = 0;

    if(len === 1) {
        return 0;
    }

    if (idx + nums[idx] + 1 >= len) {
        return 1;
    }

    while (idx < len) {
        answer += 1;

        let max = 0;
        let curIdx = 0;
        const value = nums[idx];
        console.log(value, idx)
        for (let i = idx + 1; i <= idx + value; i++) {
            if (max <= nums[i]) {
                max = nums[i];
                curIdx = i;
            }
        }

        idx += curIdx;
        console.log('ddd', curIdx, idx)
        if (idx + nums[idx] + 1 > len) {
            console.log('early return')
            return answer + 1;
        }
    }

    return answer;
};
var jump = function(nums) {

    const size = nums.length;

    // destination is last index
    let destination = size-1;

    let curCoverage = 0, lastJumpIdx = 0;

    // counter of jump
    let timesOfJump = 0;

    // Quick response if start index == destination index == 0
    if( size == 1 ){
        return 0;
    }


    // Greedy stragegy: extend coverage as long as possible with lazp jump
    for( let i = 0 ; i < size ; i++){

        // extend coverage
        curCoverage = Math.max(curCoverage, i + nums[i] );

        // forced to jump (by lazy jump) to extend coverage
        if( i == lastJumpIdx ){

            lastJumpIdx = curCoverage;

            timesOfJump++;

            // check if we reached destination already
            if( curCoverage >= destination){
                return timesOfJump;
            }
        }
    }

    return timesOfJump;
    

};
/**
 * @param {number[]} nums
 * @return {number}
 */
var jump = function (nums) {
  const len = nums.length;
  const dp = new Array(len).fill(Infinity);

  dp[0] = 0;

  for (let i = 0; i < len; i += 1) {
    const next = nums[i] + i;
    const end = Math.min(len - 1, next);

    for (let j = i; j <= end; j += 1) {
      dp[j] = Math.min(dp[i] + 1, dp[j]);
    }
  }

  return dp.at(-1);
};
var jump = function(nums) {
    const length = nums.length;
    const dp = Array(length).fill(Infinity);
    
    if(length === 1){
        return 0;
    }
    
    dp[0] = 0;
    
    for(let i = 0; i < length; i++){
        const distance = nums[i];
        const next = dp[i] + 1;
        
        for(let j = 1; j <= distance; j++){
            if(i + j >= length){
                break;
            }
            dp[i + j] = Math.min(next, dp[i + j]);
        }
    }
    
    return dp[length - 1];
};