【leetcode】45. 跳跃游戏 II
题目内容
思路分析
本题难度为困难，是55. 跳跃游戏的plus版。55题是让判断是否能到达，使用了贪心算法（尽量跳的远）。
第一眼看到这个题时，算法课学艺不精的我，打算用动态规划来做，感觉应该有可以重复利用的子问题，结果栈溢出，不断地迭代而不退出，翻车了....
本题的正确解法应该为贪心算法，有两种贪心方式，对应着两个方法。
方法一
从终点倒着往回推，每次选择离终点最远的点，也就是下标最小的点（贪心）。因此每次需要从小到大遍历数组，找到第一个可以到达当前点的点。因此算法时间复杂度为O(N^2)，空间复杂度为O(1)。
（而从前往后贪就不行？这可能就是算法课上说的贪心算法不直观吧，比如下图中的工作安排问题的不同贪心方式只有一个可用）
由于官方题解中说C++实现这种方法会超时，故没有去实现。
方法二
从前往后遍历，每次从当前可以到达的点中，选出下一跳可以到达的最远点，如下图所示（图来自官方题解）。
代码实现时，只需要维护当前可以到达的最远距离reach和下一跳可以到达的next_reach最远距离，并从前往后遍历数组。每次到达当前最远距离时，将reach更新为next_reach，并将跳数+1。由于是起跳时加跳数，因此不遍历终点（到达终点后不再起跳，因此不加条数）。使用这样的方法，将算法的时间复杂度降为了O(N)。
代码
#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <climits>
#include <algorithm>
using namespace std;
class Solution {
public:
// 官方解法 贪心算法
// 时间复杂度O(N)，空间复杂度O(1)
int jump(vector<int>& nums) {
int dst = nums.size() - 1;
int reach{ 0 }; // 能到达的最大边界
int next_reach{ 0 }; // 下一次能到达的最大边界
int jump_num{ 0 }; // 跳跃次数
for (int i = 0; i < dst; i++) { // 起跳前加步数，因此不遍历最后一个点，避免多加步数
next_reach = max(i + nums[i], next_reach);
if (i == reach) {
jump_num++;
reach = next_reach;
}
}
return jump_num;
}
// !!! 以下两个函数是自己的错误解法 想用动态规划 翻车 !!!
// 从src至dst所需的最少跳跃次数
int min_jump_num(vector<int>& nums, int src, int dst) {
// 边界条件
if (src == dst) {
return 0;
}
if (src == 0 && dst != nums.size() - 1) {
if (src + nums[src] >= dst) {
return 1;
}
else {
return INT_MAX; // 一跳不可达
}
}
int local_min_jump_num{ INT_MAX };
for (int i = src; i <= dst; ++i) {
// 可以一步到达dst
if (i + nums[i] >= dst) {
int temp = min_jump_num(nums, i, dst);
if (temp < local_min_jump_num) {
local_min_jump_num = temp + 1;
}
}
// 不可以一步到达dst则不计算(会在递归的过程中计算)
}
return local_min_jump_num;
}
int false_jump(vector<int>& nums) {
return min_jump_num(nums, 0, nums.size() - 1);
}
};
int main() {
Solution s;
vector<int> input{ 2,3,1,1,4 };
int output;
output = s.jump(input);
return output;
}
收获
学到了一种贪心算法