55. Jump Game - Medium

前往題目

想法

• 以前做過，但完全忘了😂

思路

1. 貪心演算法，從最後面開始
2. 在每個index檢查是否能到goal，如果可以的話就把當前index變為goal
3. goal最後為0的話就是可以到最後，否則一定不行

Code

class Solution {
    public boolean canJump(int[] nums) {
        int goal = nums.length - 1;

        // Greedy, start from the last index
        for (int i = nums.length - 1; i >= 0; --i) {
            // When current index can reach the goal
            // Move goal closer to the beginning
            if (i + nums[i] >= goal) {
                goal = i;
            }
        }
        return goal == 0 ? true : false;
    }
}

2024/05/03

• 沒寫出來