【LeetCode 面试经典150题】55. Jump Game 跳跃游戏
2024-01-03 13:29:49
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.
中文释义
给定一个整数数组 nums
。你最初位于数组的第一个索引处,数组中的每个元素代表你在该位置的最大跳跃长度。
如果你能到达最后一个索引,则返回 true;否则返回 false。
Example
Example 1:
- Input:
nums = [2,3,1,1,4]
- Output:
true
- Explanation: 从索引0跳1步到索引1,然后跳3步到最后一个索引。
Example 2:
- Input:
nums = [3,2,1,0,4]
- Output:
false
- Explanation: 无论如何,你总会到达索引3。该索引的最大跳跃长度为0,使得无法到达最后一个索引。
Constraints
1 <= nums.length <= 10^4
0 <= nums[i] <= 10^5
解题思路
算法描述
此代码实现了判断是否能从数组的第一个索引跳跃到最后一个索引的功能。
max_reach 记录当下能够到达的最远距离,在遍历的过程中,不断更新能够到达的最远距离max_reach,直到能够到达最后一个位置。
算法的主要步骤如下:
-
初始化变量:
max_reach
: 用于存储目前能够到达的最远索引,初始设置为0。
-
遍历数组:
- 从数组的开始遍历,直到
i
达到max_reach
或超过它。 - 在每一步中,更新
max_reach
为当前索引i
和i + nums[i]
(即当前位置能跳到的最远索引)的较大值。 - 如果在任何时候
max_reach
大于或等于数组的最后一个索引(nums.size() - 1
),则表示可以跳到最后一个索引,返回true
。
- 从数组的开始遍历,直到
-
返回结果:
- 如果遍历结束后没有能够到达最后一个索引,则返回
false
。
- 如果遍历结束后没有能够到达最后一个索引,则返回
代码示例
class Solution {
public:
bool canJump(vector<int>& nums) {
int max_reach = 0;
for (int i = 0; i <= max_reach; i++) {
max_reach = max(max_reach, i + nums[i]);
if (max_reach >= nums.size() - 1) {
return true;
}
}
return false;
}
};
文章来源:https://blog.csdn.net/qq_43513394/article/details/135361045
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!