#P4084. 跳跃游戏Ⅱ
-
ID: 2325
Tried: 212
Accepted: 95
Difficulty: 7
-
算法标签>贪心
跳跃游戏Ⅱ
题目内容
给定一个长度为 n的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说,如果你在 nums[i] 处,你可以跳转到任意 nums[i+j] 处:
- 0<=j<=nums[i]
- i+j<n
返回到达 nums[n−1]的最小跳跃次数。生成的测试用例可以到达 nums[n−1]。
输入描述
输入一个数组
输出描述
输出一个整数表示最小跳跃次数
样例1
输入
2 3 1 1 4
输出
2
说明
跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳3步到达数组的最后一个位置。
样例2
输入
2 3 0 1 4
输出
2
提示:
- 1<=nums.length<=104
- 0<=nums[i]<=1000
- 题目保证可以到达 nums[n−1]
题解
题面描述
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说,如果你在 nums[i] 处,你可以跳转到任意 nums[i+j] 处,其中 0leqjleqnums[i] 且 i+j<n。
返回到达 nums[n−1] 的最小跳跃次数。题目保证可以到达 nums[n−1]。
思路
采用贪心算法:
- 使用两个变量:end 表示当前跳跃能到达的最远边界,maxReach 表示遍历过程中能跳跃到的最远位置。
- 当遍历到当前边界时,说明需要跳跃一次,将跳跃次数加 1,并更新边界为 maxReach。
- 遍历过程中不断更新 maxReach=max(maxReach,i+nums[i])。
- 当边界达到或超过 n−1 时,即可得到最小跳跃次数。
代码分析
- 贪心策略本质:每次尽可能向前跳,使得在下一步中能够覆盖最大的范围,从而达到最少跳跃次数。
- 时间复杂度:O(n),只需要遍历数组一次。
- 空间复杂度:O(1),只使用常数空间。
C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
// 函数 jump 返回到达最后一个位置的最小跳跃次数
int jump(vector<int>& nums) {
int n = nums.size();
// 如果数组大小为 1,则不需要跳跃
if(n < 2) return 0;
int jumps = 0; // 跳跃次数
int maxReach = 0; // 当前能到达的最远位置
int end = 0; // 当前跳跃的边界
for (int i = 0; i < n - 1; i++) {
maxReach = max(maxReach, i + nums[i]); // 更新最大能到达的位置
// 当遍历到当前边界时,需要跳跃一次
if (i == end) {
jumps++;
end = maxReach;
}
}
return jumps;
}
};
int main(){
vector<int> nums;
int num;
// 读取一行输入,直到输入结束
while(cin >> num) {
nums.push_back(num);
}
Solution sol;
cout << sol.jump(nums) << endl;
return 0;
}
Python
# 定义 Solution 类,包含 jump 方法
class Solution:
def jump(self, nums):
# 获取数组长度
n = len(nums)
# 如果数组长度小于 2,则不需要跳跃
if n < 2:
return 0
jumps = 0 # 跳跃次数
maxReach = 0 # 当前能到达的最远位置
end = 0 # 当前跳跃的边界
# 遍历数组,不包括最后一个位置
for i in range(n - 1):
# 更新最大能到达的位置
maxReach = max(maxReach, i + nums[i])
# 当到达当前边界时,需要进行一次跳跃
if i == end:
jumps += 1
end = maxReach
return jumps
if __name__ == "__main__":
# 从标准输入读取一行数据,分割成整数列表
import sys
nums = list(map(int, sys.stdin.read().strip().split()))
sol = Solution()
print(sol.jump(nums))
Java
import java.util.*;
import java.io.*;
public class Main {
// 定义 Solution 类,包含 jump 方法
static class Solution {
// 方法 jump 返回到达最后一个位置的最小跳跃次数
public int jump(int[] nums) {
int n = nums.length;
// 如果数组长度小于 2,则不需要跳跃
if(n < 2) return 0;
int jumps = 0; // 跳跃次数
int maxReach = 0; // 当前能到达的最远位置
int end = 0; // 当前跳跃的边界
// 遍历数组,不包括最后一个位置
for (int i = 0; i < n - 1; i++) {
// 更新最大能到达的位置
maxReach = Math.max(maxReach, i + nums[i]);
// 当到达当前边界时,需要进行一次跳跃
if (i == end) {
jumps++;
end = maxReach;
}
}
return jumps;
}
}
public static void main(String[] args) throws IOException {
// 使用 Scanner 读取标准输入
Scanner sc = new Scanner(System.in);
ArrayList<Integer> list = new ArrayList<>();
// 逐个读取整数
while(sc.hasNextInt()){
list.add(sc.nextInt());
}
int[] nums = new int[list.size()];
for (int i = 0; i < list.size(); i++) {
nums[i] = list.get(i);
}
Solution sol = new Solution();
// 输出结果到标准输出
System.out.println(sol.jump(nums));
sc.close();
}
}