跳跃游戏系列（LeetCode Jump Game I-V）
用到的思路包括：贪心、广搜、递归。
题目较多，就不贴原题了，点击标题直接跳转查看。
LeetCode 55. Jump Game I
这道题给出的数组元素表示当前位置最大可跳距离，问能否从第一个位置到达最后一个位置。
BFS 是会超时的，需要 O(N) 的解法，贪心就是。
直接用一个变量记录最大可达到的范围，然后不断更新这个值。如果到达末尾前就卡在某一个下标无法前进，则最后一个位置不可达。
参考代码：
/*
* @lc app=leetcode id=55 lang=cpp
*
* [55] Jump Game
*/
// @lc code=start
class Solution {
public:
bool canJump(vector<int>& nums) {
assert(!nums.empty());
int n = nums.size();
int canReach = 0;
for (int i = 0; i < n; i++) {
if (canReach < i) return false;
if (canReach >= n-1) return true;
canReach = max(canReach, i + nums[i]);
} // greedy algorithm
return canReach >= n-1;
}
};
// @lc code=end
LeetCode 45. Jump Game II
这一题给出了最大跳跃能力，问从第一个位置到达最后一个位置至少需要跳几次。
这道题用 DP 和 BFS 都超时了，需要的是 O(N) 复杂读的做法。贪心可以。
用一个变量 nextMaxReach 记录下一步可以到达的最远距离，通过访问 curMaxReach 以内的所有点来更新这个距离得到最大值；然后 step++ 进入下一步，切换到 nextMaxReach 里继续进行。
参考代码：
/*
* @lc app=leetcode id=45 lang=cpp
*
* [45] Jump Game II
*/
// @lc code=start
class Solution {
// assume that you can always reach the last index.
public:
int jump(vector<int>& nums) {
assert(!nums.empty());
if (nums.size() == 1) return 0;
size_t n = nums.size();
int curMaxReach = 0;
int nextMaxReach = 0;
int step = 0;
int i = 0;
while (i < n) {
while (i <= curMaxReach) {
nextMaxReach = max(nextMaxReach, i + nums[i]);
if (nextMaxReach >= n-1) return step+1;
i++;
}
step++;
curMaxReach = nextMaxReach;
} // greedy, find max dist can reach in given steps
return -1;
} // AC
};
// @lc code=end
LeetCode 1306. Jump Game III
这道题固定了跳跃距离只能是给定的距离，可以选择往前跳还是往后跳。问是否可以跳转到元素0所在位置。
简单 BFS 即可，类似走迷宫问题。所有位置最多访问一次，时间复杂度 O(N)。
参考代码：
/*
* @lc app=leetcode id=1306 lang=cpp
*
* [1306] Jump Game III
*/
// @lc code=start
class Solution {
public:
bool canReach(vector<int>& arr, int start) {
assert(0 <= start && start < arr.size());
if (arr[start] == 0) return true;
size_t n = arr.size();
queue<int> q;
vector<bool> vis(n, false);
q.push(start);
vis[start] = true;
while (!q.empty()) {
int i = q.front();
q.pop();
if (i + arr[i] < n && !vis[i + arr[i]]) {
if (arr[ i+arr[i] ] == 0) return true;
q.push(i+arr[i]);
vis[i+arr[i]] = true;
}
if (0 <= i - arr[i] && !vis[i - arr[i]]) {
if (arr[ i-arr[i] ] == 0) return true;
q.push(i-arr[i]);
vis[i-arr[i]] = true;
}
}
return false;
} // AC, BFS
};
// @lc code=end
LeetCode 1345. Jump Game IV
这道题加了一个“任意门”，可以选择往前跳一格、往后跳一格，或者跳转到与当前元素值相同的位置上。问从第一个位置到达最后一个位置至少需要跳几次。
一道典型的 BFS 题目，类似于走迷宫问题。使用 queue 来保存顺序，先到的一定是最快的。
注意这里原始的 BFS 会超时，应该注意优化：连续 [7,7,7,7,7] 之类其实只有首尾两个位置是有用的；同一个任意门只有第一次跳转是有用的。
unordered_map 套 vector 也是很有趣的用法，比 unordered_multimap 好用。
参考代码：
/*
* @lc app=leetcode id=1345 lang=cpp
*
* [1345] Jump Game IV
*/
// @lc code=start
class Solution {
public:
int minJumps(vector<int>& arr) {
assert(!arr.empty());
if (arr.size() == 1) return 0;
size_t n = arr.size();
queue<pair<int, int>> q;
vector<bool> vis(n, false);
// unordered_map<vector> is better than unordered_multimap in
// insert elements & for-range specified key & erase key
unordered_map<int, vector<int>> val2idx;
for (int i = 0; i < n; i++) {
if (0 <= i-1 && arr[i-1] == arr[i]
&& i+1 < n && arr[i] == arr[i+1]) {
vis[i] = true;
continue;
} // [7,7,7] only 1st and last useful, or TLE
val2idx[arr[i]].push_back(i);
}
q.push({0, 0});
vis[0] = true;
while (!q.empty()) {
auto&& p = q.front();;
int i = p.first;
int step = p.second;
q.pop();
if (0 <= i-1 && !vis[i-1]) {
q.push({i-1, step+1});
vis[i-1] = true;
}
if (i+1 < n && !vis[i+1]) {
if (i+1 == n-1) return step+1;
q.push({i+1, step+1});
vis[i+1] = true;
}
for (int x : val2idx[arr[i]]) {
if (x == i || vis[x]) continue;
if (x == n-1) return step+1;
q.push({x, step+1});
vis[x] = true;
}
val2idx[arr[i]] = {}; // key optimization
}
return -1;
}
};
// @lc code=end
另一种写法
注意到 queue 中其实 step 是有规律的，有一种写法可以 queue 只保存 index 而不用保存 step，节省一半空间。参考 花花酱的解答：
- 只用一个 int 变量保存当前 step
- 每次检查
while(!q.empty())之后记录k=q.size()，然后把队列中前 k 个元素弹出做计算。这 k 个元素的步数 其实都是 step，下一轮的元素都是 step+1。
LeetCode 1340. Jump Game V
这道题把数组元素值设定为台阶高度，然后指定横向最大跳远能力，并限制跳远时只能往下落，不能跳到或经过更高的台阶。问从任意位置出发，最多能踩到几个台阶。
这就是一道典型的 DP 问题了。以每个台阶为起点的最大跳台阶数目，由左右两边 d 以内比自己低的台阶决定。由于高台阶依赖于低台阶的结果，我们需要先做一个排序的预处理，由此来决定计算顺序。时间复杂度 O(d*N+NlogN)。
/*
* @lc app=leetcode id=1340 lang=cpp
*
* [1340] Jump Game V
*/
// @lc code=start
class Solution {
public:
int maxJumps(vector<int>& arr, int d) {
assert(!arr.empty() && d >= 1);
size_t n = arr.size();
vector<pair<int,int>> v;
for (int i = 0; i < n; i++) {
v.push_back({arr[i], i});
}
sort(v.begin(), v.end()); // sort by height
vector<int> dp(n, 1);
for (auto&& [h, i] : v) {
for (int k = 1; k <= d; k++) { // ->
int j = i + k;
if (j >= n || arr[j] >= arr[i]) break;
dp[i] = max(dp[i], dp[j] + 1);
}
for (int k = 1; k <= d; k++) { // <-
int j = i - k;
if (0 > j || arr[j] >= arr[i]) break;
dp[i] = max(dp[i], dp[j] + 1);
}
}
int res = 1;
for (int x : dp) {
res = max(res, x);
}
return res;
} // AC, DP
};
// @lc code=end