题解 |跳跃游戏(一)
跳跃游戏(一)
https://www.nowcoder.com/practice/07484f4377344d3590045a095910992b
解题思路
这是一个判断能否跳到数组末尾的问题，可以通过贪心算法来解决：
- 维护一个变量
，表示当前能够到达的最远位置
- 遍历数组，对于每个位置
：
- 如果
- 更新
- 如果
- 如果能遍历完整个数组，说明可以到达末尾
代码
#include <iostream>
#include <vector>
using namespace std;
bool canJump(vector<int>& nums) {
int n = nums.size();
int maxReach = 0; // 当前能到达的最远位置
for (int i = 0; i <= maxReach; i++) {
// 如果已经可以到达最后一个位置
if (maxReach >= n - 1) return true;
// 更新最远可达位置
maxReach = max(maxReach, i + nums[i]);
}
return false;
}
int main() {
int n;
cin >> n;
vector<int> nums(n);
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
cout << (canJump(nums) ? "true" : "false") << endl;
return 0;
}
import java.util.*;
public class Main {
public static boolean canJump(int[] nums) {
int n = nums.length;
int maxReach = 0;
for (int i = 0; i <= maxReach; i++) {
if (maxReach >= n - 1) return true;
maxReach = Math.max(maxReach, i + nums[i]);
}
return false;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = sc.nextInt();
}
System.out.println(canJump(nums) ? "true" : "false");
}
}
def canJump(nums):
n = len(nums)
max_reach = 0 # 当前能到达的最远位置
for i in range(n):
# 如果当前位置已经超过了能到达的最远位置
if i > max_reach:
return False
# 更新最远可达位置
max_reach = max(max_reach, i + nums[i])
# 如果已经可以到达最后一个位置
if max_reach >= n - 1:
return True
return True
n = int(input())
nums = list(map(int, input().split()))
print("true" if canJump(nums) else "false")
算法及复杂度
- 算法：贪心算法
- 时间复杂度：
- 只需要遍历一次数组
- 空间复杂度：
- 只需要常数额外空间
这道题的关键在于理解贪心的思想：我们只需要关心在当前位置能跳到的最远距离。对于每个位置，我们都更新能到达的最远位置，如果在遍历过程中发现当前位置已经超过了能到达的最远位置，就说明无法到达终点。
几个重要的点：
- 遍历时需要判断当前位置
）
- 对于每个可达位置，更新
- 如果在遍历过程中
，说明可以到达终点
这种贪心的方法比动态规划更高效，因为我们只需要遍历一次数组，并且只需要维护一个变量。