[LeetCode 55] Jump Game with JAVA

leetcode.com/problems/jump-game/

Jump Game - LeetCode

Given an array of non-negative integers nums, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

 

Example 1:

Input: nums = [2,3,1,1,4] Output: true Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [3,2,1,0,4] Output: false Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

 

Constraints:

• 1 <= nums.length <= 3 * 104
• 0 <= nums[i] <= 105

 

class Solution {
    public boolean canJump(int[] nums) {
        int N = nums.length;
        int end = 0;
        for (int i = 0; i < N; i++){
            int step = nums[i];
            end = Math.max(i + step, end);
            if (end >= N - 1){
                return true;
            }
            else if (end == i) return false;
        }
        return true;
    }
}

1. 어려웠던 점:

- partition labels를 풀지 않았으면 접근법을 못찾았을 것 같다.

2. 알게된 점:

- 그리디 복습

 

3. 알고리즘 풀이:

- 첫 인덱스부터 갈 수 있는 최대 인덱스를 저장한다. 초깃값은 0, 변수는 end

지금 인덱스에서, 걸어갈 수 있는 최대 걸음수를 간 것이 end보다 큰 지 비교하고 더 큰 값을 end에 넣어준다.

end가 배열 마지막 인덱스보다 같거나 크면, 마지막 인덱스에 갈 수 있으므로 return true

그렇지 않고, end와 for문의 i값이 같아지면, 0부터 걸었을 때, 최대 한대값에 도달했으므로 return false