跳跃游戏 II 中等🌟🌟🌟🌟🌟
课后作业
问题描述
原文链接：45. 跳跃游戏 II
给定一个长度为 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:
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
示例 2:
输入: nums = [2,3,0,1,4]
输出: 2
提示:
1 <= nums.length <= 1040 <= nums[i] <= 1000- 题目保证可以到达
nums[n-1]
代码实现
Java
class Solution {
// public int jump(int[] nums) {
// int start = 0;
// int end =0;
// int res = 0;
// int max = 0;
// // 时间：On
// while(end < nums.length){
// if(max >= nums.length - 1) return res;
// // i从来没有重复过，是可以去掉 while 循环
// for(int i = start; i <= end; i++){
// max = Math.max(max, i + nums[i]);
// }
// // 每次选取完就相当于跳跃了一步
// res ++;
// // 更新一些边界
// start = end + 1;
// end = max;
// }
// return res;
// }
public int jump(int[] nums) {
int end =0;
int res = 0;
int max = 0;
for(int i =0; i < nums.length - 1; i++){
//if(max >= nums.length - 1) return res;
max = Math.max(max, i + nums[i]);
if(i == end){
end = max;
res ++;
}
}
return res;
}
}
Python
class Solution(object):
def jump(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
end = 0
res = 0
max_pos = 0
for i in range(len(nums) - 1):
max_pos = max(max_pos, i + nums[i])
if i == end:
end = max_pos
res += 1
return res
C++
class Solution {
public:
int jump(vector<int>& nums) {
int end = 0;
int res = 0;
int max_pos = 0;
for (int i = 0; i < nums.size() - 1; i++) {
//if (max_pos >= nums.size() - 1) return res;
max_pos = max(max_pos, i + nums[i]);
if (i == end) {
end = max_pos;
res++;
}
}
return res;
}
};
Go
func jump(nums []int) int {
end := 0
res := 0
maxPos := 0
for i := 0; i < len(nums)-1; i++ {
//if maxPos >= len(nums)-1 {
// return res
//}
maxPos = max(maxPos, i+nums[i])
if i == end {
end = maxPos
res++
}
}
return res
}
// 辅助函数，返回较大值
func max(a, b int) int {
if a > b {
return a
}
return b
}