LeetCode 0055 - Jump Game
# Hints
- 贪心
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Medium |
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
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:
# 题意
给定一个长为 的非负整数数组 ,下标从 起,初始站在 处,从 出发可以跳到区间 内的任意一点,判断跳任意次后是否能跳到 处。
# 题解
水题,遍历数组并贪心地更新最远可达距离即可。
# AC代码
class Solution {
public:
bool canJump(vector<int> & nums) {
// 求解
int farest = 0;
for (int i = 0; i < nums.size(); i ++) {
// 失败的情况
if (i > farest) {
return false;
}
// 更新
farest = max(farest, i + nums[i]);
}
// 返回
return true;
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01