#P4030. 跳跃游戏
-
ID: 2246
Tried: 102
Accepted: 33
Difficulty: 4
-
算法标签>贪心
跳跃游戏
题目内容
给你一个非负整数数组 nums ，你最初位于数组的第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
输入描述
输出描述
样例1
输入
2 3 1 1 4
输出
true
说明
可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标1 跳 3步到达最后一个下标。
样例2
输入
3 2 1 0 4
输出
flase
说明
无论怎样，总会到达下标为 3的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
提示
- 1<=nums.length<=104
- 0<=nums[i]<=105
题解
题面描述
给定一个非负整数数组 nums，数组中每个元素表示当前位置可以跳跃的最大步数。初始时你位于数组的第一个下标，判断是否能够跳跃到最后一个下标。如果可以，返回 true；否则返回 false。
思路
我们可以使用贪心算法：
- 定义变量 max_reach 表示当前能跳跃到的最远下标。
- 遍历数组，对于每个下标 i：
- 若 i>max_reach，说明下标 i 不可达，直接返回 false；
- 否则更新 max_reach=max(max_reach,i+nums[i])；
- 如果最终 max_reach 大于或等于数组的最后一个下标，则返回 true，否则返回 false。
这种方法的时间复杂度为 O(n)，空间复杂度为 O(1)。
代码分析
- 变量定义：max_reach 用来记录目前可以到达的最远位置。
- 更新过程：对于每个下标 i，如果 i 在 max_reach 之内，则更新 max_reach 为 max(max_reach,i+nums[i])。
- 终止条件：如果在遍历过程中发现 i>max_reach，则意味着当前位置不可达，直接返回 false。遍历结束后，如果 max_reach 大于等于最后一个下标，说明可达最后一个位置。
问题本质分析
该问题的本质是贪心策略，通过每一步的最优选择（即更新能到达的最远位置）来判断整个数组是否可以遍历到末尾。关键在于：
- 能否在遍历过程中保持连续的可达区间。
- 及时更新能跳跃的最远位置，避免陷入无法前进的状态。
C++
#include <iostream>
#include <vector>
#include <sstream>
#include <algorithm>
using namespace std;
class Solution {
public:
// 判断是否可以跳到最后一个下标
bool canJump(vector<int>& nums) {
int max_reach = 0; // 当前可跳跃的最远下标
int n = nums.size();
for (int i = 0; i < n; i++) {
// 如果当前位置不可达，则返回 false
if (i > max_reach) return false;
// 更新最远可以到达的下标
max_reach = max(max_reach, i + nums[i]);
// 如果已经可以到达最后一个下标，则直接返回 true
if (max_reach >= n - 1) return true;
}
return false;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string line;
// 读取一整行输入
getline(cin, line);
istringstream iss(line);
vector<int> nums;
int num;
// 分割字符串获得每个数字
while (iss >> num) {
nums.push_back(num);
}
Solution sol;
// 根据判断结果输出 true 或 false
cout << (sol.canJump(nums) ? "true" : "false") << "\n";
return 0;
}
Python
# 定义 Solution 类
class Solution:
def canJump(self, nums: list) -> bool:
max_reach = 0 # 当前可以跳跃到的最远下标
n = len(nums)
for i in range(n):
# 如果当前位置不可达，则返回 False
if i > max_reach:
return False
# 更新最远可以到达的下标
max_reach = max(max_reach, i + nums[i])
# 如果可以到达最后一个下标，直接返回 True
if max_reach >= n - 1:
return True
return False
if __name__ == '__main__':
import sys
# 读取标准输入中的一行数据
line = sys.stdin.readline().strip()
# 将输入字符串分割为整数列表
nums = list(map(int, line.split()))
sol = Solution()
# 输出判断结果
print("true" if sol.canJump(nums) else "false")
Java
import java.util.Scanner;
public class Main {
// 定义 Solution 类
static class Solution {
public boolean canJump(int[] nums) {
int maxReach = 0; // 当前可以跳跃到的最远下标
int n = nums.length;
for (int i = 0; i < n; i++) {
// 如果当前位置不可达，则返回 false
if (i > maxReach) return false;
// 更新最远可以到达的下标
maxReach = Math.max(maxReach, i + nums[i]);
// 如果可以到达最后一个下标，直接返回 true
if (maxReach >= n - 1) return true;
}
return false;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 读取整行输入
String line = sc.nextLine();
String[] parts = line.split(" ");
int n = parts.length;
int[] nums = new int[n];
// 将字符串数组转换为整数数组
for (int i = 0; i < n; i++) {
nums[i] = Integer.parseInt(parts[i]);
}
Solution sol = new Solution();
// 根据判断结果输出 "true" 或 "false"
System.out.println(sol.canJump(nums) ? "true" : "false");
sc.close();
}
}