[LeetCode] 45. Jump Game II

https://leetcode.com/

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:

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.

 

Example 2:

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

 

Constraints:

• 1 <= nums.length <= 10^4
• 0 <= nums[i] <= 1000
• It's guaranteed that you can reach nums[n - 1].

 

Code :

var jump = function(nums) {
    let n = nums.length;
    if (n < 2) return 0; // 배열의 길이가 1 이하면 0 반환

    let maxPosition = nums[0]; // 현재 위치에서 갈 수 있는 최대 위치
    let maxSteps = nums[0]; // 갈 수 있는 최대 거리
    let jumps = 1; // 점프 수

    for (let i = 1; i < n; i++) {
        if (maxSteps < i) {
            // 최대 거리가 현재 위치보다 작을 경우 점프 수를 증가시키고 최대 거리를 갱신
            jumps++;
            maxSteps = maxPosition;
        }
        // 현재 위치에서 갈 수 있는 최대 위치 갱신
        maxPosition = Math.max(maxPosition, nums[i] + i);
    }

    return jumps; // 점프 수 반환
};

 

Solutions Code :

var jump = function(nums) {
    const size = nums.length;
    // 목적지는 마지막 인덱스
    let destination = size-1;
    let curCoverage = 0, lastJumpIdx = 0;
    // 점프 횟수를 세는 변수
    let timesOfJump = 0;
    // 시작 인덱스와 도착 인덱스가 0인 경우 빠른 응답
    if( size == 1 ){
        return 0;
    }
    // 탐욕 전략: 최대한 먼 거리로 점프하여 범위를 확장
    for( let i = 0 ; i < size ; i++){
        // 범위 확장
        curCoverage = Math.max(curCoverage, i + nums[i] );
        // 범위를 확장하기 위해 (게으른 점프로) 점프해야 하는 경우
        if( i == lastJumpIdx ){
            lastJumpIdx = curCoverage;
            timesOfJump++;
            // 이미 도착지에 도달한 경우를 확인
            if( curCoverage >= destination){
                return timesOfJump;
            }
        }
    }
    return timesOfJump;
};

 

 

출처 : https://leetcode.com/problemset/all/

Problems - LeetCode