Skip to content

LeetCode: 55-Jump Game 解題紀錄

Last Updated on 2022-12-26 by Clay

題目

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.

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 <= 104
  • 0 <= nums[i] <= 105

題目給定一個數值陣列,陣列中的每一個元素是我們可以『跳躍』的最長距離(亦即我們可以跳到這個距離內的任意點)。我們從 index 0 開始出發,要判斷最終是否能跳躍到陣列的最後一個元素。


解題思路

更新可抵達的最遠跳躍點

設定了一個儲存最遠眺遠點的變數,該變數第一個儲存的位值是 0,也就是起點。接著設定一個 while 迴圈,迴圈的成立條件為當前位置小於等於最遠跳躍點,當前位置也是從 0 開始走,每次都要判斷『當前位置』加上『可跳躍距離』是否大於當前的最遠跳躍點,如果大於最遠跳躍點,也要及時更新。

如果最後最遠跳躍點能大於等於最後一個元素的位置,則回傳 true;反之則回傳 false


更新可抵達的最遠跳躍點 複雜度

Time ComplexityO(n)
Space ComplexityO(1)


C++ 範例程式碼

class Solution {
public:
    bool canJump(vector<int>& nums) {
        // Init
        int maxJumpPos = 0;
        int last = nums.size() - 1;
        int i = 0;

        // Reaching
        while (i <= maxJumpPos) {
            // Update `maxJumpPos`
            maxJumpPos = max(maxJumpPos, nums[i]+i);

            // If we can jump over the last element
            if (maxJumpPos >= last) {
                return true;
            }

            // Step
            ++i;
        }

        return false;
    }
};



Python 範例程式碼

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        # Init
        maxJumpPos = 0
        last = len(nums) - 1
        i = 0

        # Reaching
        while i <= maxJumpPos:
            # Update `maxJumpPos`
            maxJumpPos = max(maxJumpPos, nums[i]+i)

            # If can jump over the last
            if maxJumpPos >= last:
                return True

            # Step
            i += 1

        return False

References


Read More

Leave a Reply取消回覆

Exit mobile version