LeetCode //55. Jump Game-Toy模板网

这篇具有很好参考价值的文章主要介绍了LeetCode //55. Jump Game。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

55. Jump Game

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 <= 10^4$
$0 <= nums[i] <= 10^5$

From: LeetCode
Link: 55. Jump Game文章来源地址https://www.toymoban.com/news/detail-573519.html

Solution:

Ideas：

Initialize lastPos to the last index of the array. This is the target we want to reach.
Loop backwards through the array.
For each index i, check if we can jump from that index to lastPos or further.
If so, update lastPos to i. This means we know we can reach index i, and just need to check if we can reach i from before.
After looping, if lastPos is 0, it means we can reach the start, so return true.
If lastPos is not 0, we cannot reach the start, so return false.

Code:

bool canJump(int* nums, int numsSize){
  int lastPos = numsSize - 1;
  for(int i = numsSize - 1; i >= 0; i--){
    if(i + nums[i] >= lastPos){
      lastPos = i;
    }
  }
  return lastPos == 0; 
}