请选择 进入手机版 | 继续访问电脑版
MSIPO技术圈 首页 IT技术 查看内容

LeetCode //55. Jump Game

2023-07-13

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 < = n u m s . l e n g t h < = 1 0 4 1 <= nums.length <= 10^4 1<=nums.length<=104
  • 0 < = n u m s [ i ] < = 1 0 5 0 <= nums[i] <= 10^5 0<=nums[i]<=105

From: LeetCode
Link: 55. Jump Game


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; 
}

相关阅读

热门文章

    手机版|MSIPO技术圈 皖ICP备19022944号-2

    Copyright © 2024, msipo.com

    返回顶部