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 <= 1040 <= nums[i] <= 105
題目給定一個數值陣列，陣列中的每一個元素是我們可以『跳躍』的最長距離（亦即我們可以跳到這個距離內的任意點）。我們從 index 0 開始出發，要判斷最終是否能跳躍到陣列的最後一個元素。
解題思路
更新可抵達的最遠跳躍點
設定了一個儲存最遠眺遠點的變數，該變數第一個儲存的位值是 0，也就是起點。接著設定一個 while 迴圈，迴圈的成立條件為當前位置小於等於最遠跳躍點，當前位置也是從 0 開始走，每次都要判斷『當前位置』加上『可跳躍距離』是否大於當前的最遠跳躍點，如果大於最遠跳躍點，也要及時更新。
如果最後最遠跳躍點能大於等於最後一個元素的位置，則回傳 true；反之則回傳 false。
更新可抵達的最遠跳躍點 複雜度
| Time Complexity | O(n) |
| Space Complexity | O(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