题目
45. 跳跃游戏 II
给定一个长度为 n 的 0 索引整数数组 nums。初始位置在下标 0。
每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在索引 i 处，你可以跳转到任意 (i + j) 处：
- 0 <= j <= nums[i] 且
- i + j < n
返回到达 n – 1 的最小跳跃次数。测试用例保证可以到达 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 <= 104
- 0 <= nums[i] <= 1000
- 题目保证可以到达 n – 1
我的代码（Python）
version I
function innerJump(start_idx: number, nums: number[]): number {
if (start_idx >= nums.length - 1) {
return 0;
}
if (nums[start_idx] == 0) {
return 10000;
}
if (start_idx + nums[start_idx] >= nums.length - 1) {
return 1;
}
let result = 1 + innerJump(start_idx + 1, nums);
for (let i = start_idx + 2; i <= start_idx + nums[start_idx] && i < nums.length; i++) {
result = Math.min(1 + innerJump(i, nums), result);
}
return result;
}
function jump(nums: number[]): number {
return innerJump(0, nums);
};最直接的想法，递归，但是超时了。
这种做法相当于长度有多少，就要递归多少层。
version II
function jump(nums: number[]): number {
if (nums.length <= 1) {
return 0;
}
let cntArray = new Array(nums.length).fill(0);
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j <= i + nums[i] && j < nums.length; j++) {
if (cntArray[j] == 0) {
cntArray[j] = cntArray[i] + 1;
} else {
cntArray[j] = Math.min(cntArray[j], cntArray[i] + 1);
}
}
}
return cntArray[nums.length - 1];
};从前往后计算每一项的最小步骤数。
通过了，但是效率不够。
思路应该是对的，但是还有优化空间。
version III
function jump(nums: number[]): number {
if (nums.length <= 1) {
return 0;
}
let cntArray = new Array(nums.length).fill(0);
let start = 0;
let end = Math.min(nums[0], nums.length - 1);
while (start < end && end < nums.length) {
let maxRange = 0;
for (let j = start + 1; j <= end; j++) {
cntArray[j] = cntArray[start] + 1;
maxRange = Math.max(maxRange, nums[j] + j);
}
start = end;
end = Math.min(maxRange, nums.length - 1);
}
return cntArray[nums.length - 1];
};优化之后略有提升，还j不够好。
点评
对照官方解法，我的第三个版本相当于解法2，从前向后的贪心算法。
不过我做了多余的操作：没必要每个位置都赋值的，只要求最后一个位置的步数，用一个变量计数就好了。
baddif@gmail.com
AI简历优化站
AI求职跟踪器（建设中）
主站（建设中）
相关平台
Github Issues / Notion / Blog