LeetCode 55. Jump Game
You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.
Return true if you can reach the last index, or false otherwise.
Example 1:
Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.Example 2:
Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.method 1: 贪心
bool canJump(vector<int>& nums) {
int dist = 0; // 记录当前所能跳到的最远距离
int n = nums.size();
for (int i = 0; i < n; i++) {
if (dist < i) return false; // 最远距离小于i，说明到不了i
dist = max(dist, i + nums[i]);
}
return true;
}method 2: 动态规划
dp[i]表示从下标0到i能跳到的最远的位置
首先肯定可以跳到i+nums[i]的位置，其次，如果i-1的dp[i-1]能跳到的位置比i+nums[i]还要远，等价于dp[i]也能跳那么远，所以递推公式
dp[i] = max(dp[i-1], i + nums[i])bool canJump(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n);
dp[0] = nums[0];
for (int i = 1; i < n; i++) {
if (dp[i - 1] < i) return false; // 跳不到当前位置
dp[i] = max(dp[i - 1], i + nums[i]);
}
return true;
}LeetCode 45. Jump Game II
Given an array of non-negative integers nums, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
You can assume that you can always reach the last index.
Example 1:
Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.method 1: 动态规划
dp[i]：跳到i所需要的最少步数i能跳到i+1,i+2,...,i+nums[i]，所以可以对它能跳到的这些做更新
| idx | 0 | 1 | 2 | 3 |
| nums | 2 | 3 | 1 | 1 |
| dp | 0 | inf | inf | inf |
i=0可以跳2步，所以可以对i+1=1和i+2=2做更新
| idx | 0 | 1 | 2 | 3 |
| nums | 2 | 3 | 1 | 1 |
| dp | 0 | 1 | 1 | inf |
i=1可以跳3步，所以可以对i+1=2和i+2=3做更新，i+3=4>=n越界了，说明可以跳到n-1了
| idx | 0 | 1 | 2 | 3 |
| nums | 2 | 3 | 1 | 1 |
| dp | 0 | 1 | 1 | 2 |
const int inf = 0x3f3f3f3f;
int jump(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n, inf);
dp[0] = 0;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j <= i + nums[i]; j++) {
if (j >= n) return dp[n - 1]; // 能跳到n，肯定也能到n-1，直接返回，必须写，不然会溢出
dp[j] = min(dp[j], dp[i] + 1);
}
}
return dp[n - 1];
}题目保证可以跳到，如果跳不到，dp[n-1]就不会被更新，最后根据dp[n-1]来判断是否可以跳到
const int N = 1e5+5;
const int inf = 0x3f3f3f3f;
int nums[N], dp[N];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> nums[i];
memset(dp, 0x3f, sizeof(dp));
dp[0] = 0;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j <= i + nums[i]; j++) {
if (j >= n) break; // 肯定跳得到
dp[j] = min(dp[j], dp[i] + 1);
}
}
if (dp[n - 1] == inf) cout << -1; // 跳不到
else cout << dp[n - 1]; // 跳得到
return 0;
}method 2: 贪心
每次记录能跳到的最远距离maxEnd，只有遍历到这个最远距离i==maxEnd的时候步数才会增加
int jump(vector<int>& nums) {
int step = 0, maxNext = 0, maxEnd = 0;
for (int i = 0; i < nums.size() - 1; i++) {
maxNext = max(maxNext, i + nums[i]);
if (i == maxEnd) { // 走到了最远距离处才增加步数
step++;
maxEnd = maxNext;
}
}
return step;
}i=0时，能跳到的最远位置是maxNext=2，此时maxEnd=i，所以需要做一次起跳，然后在i=1~2的时候做第二次起跳，期间会更新maxNext，作为下一次起跳的maxEnd
如果跳不到，最后maxEnd就到不了n-1的位置，以此作为判断
const int N = 1e5+5;
int nums[N];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> nums[i];
if (n == 1) {
cout << 0;
return 0;
}
int step = 0;
int maxNext = 0, maxEnd = 0;
for (int i = 0; i < n - 1; i++) {
maxNext = max(maxNext, i + nums[i]);
if (i == maxEnd) {
step++;
maxEnd = maxNext;
}
}
if (maxEnd < n - 1) cout << -1; // 跳不到
else cout << step;
return 0;
}LeetCode 1306. 跳跃游戏 III
这里有一个非负整数数组 arr，你最开始位于该数组的起始下标 start 处。当你位于下标 i 处时，你可以跳到 i + arr[i] 或者 i - arr[i]。
请你判断自己是否能够跳到对应元素值为 0 的任一下标处。
注意，不管是什么情况下，你都无法跳到数组之外。
示例 1：
输入：arr = [4,2,3,0,3,1,2], start = 5
输出：true
解释：
到达值为 0 的下标 3 有以下可能方案：
下标 5 -> 下标 4 -> 下标 1 -> 下标 3
下标 5 -> 下标 6 -> 下标 4 -> 下标 1 -> 下标 3method 1: DFS
used数组标记该下标是否访问过
bool dfs(vector<int>& nums, int index, vector<bool>& used) {
if (index < 0 || index >= nums.size() || used[index]) return false;
if (nums[index] == 0) return true;
used[index] = 1;
if (dfs(nums, index + nums[index], used)) return true;
if (dfs(nums, index - nums[index], used)) return true;
// used[index] = 0; // 可以不用回溯
return false;
}
bool canReach(vector<int>& arr, int start) {
vector<bool> used(arr.size(), false);
return dfs(arr, start, used);
}method 2: BFS
bool canReach(vector<int>& nums, int start) {
int n = nums.size();
vector<int> used(n, false);
queue<int> q;
q.push(start);
while (!q.empty()) {
int x = q.front();
q.pop();
if (nums[x] == 0) return true;
if (x + nums[x] < n && !used[x + nums[x]]) {
used[x + nums[x]] = true;
q.push(x + nums[x]);
}
if (x - nums[x] >= 0 && !used[x - nums[x]]) {
used[x - nums[x]] = true;
q.push(x - nums[x]);
}
}
return false;
}LeetCode 1345. 跳跃游戏 IV
给你一个整数数组 arr ，你一开始在数组的第一个元素处（下标为 0）。
每一步，你可以从下标 i 跳到下标 i + 1 、i - 1 或者 j ：
i + 1需满足：i + 1 < arr.lengthi - 1需满足：i - 1 >= 0j需满足：arr[i] == arr[j]且i != j
请你返回到达数组最后一个元素的下标处所需的 最少操作次数 。
注意：任何时候你都不能跳到数组外面。
示例 1：
输入：arr = [100,-23,-23,404,100,23,23,23,3,404]
输出：3
解释：那你需要跳跃 3 次，下标依次为 0 --> 4 --> 3 --> 9 。下标 9 为数组的最后一个元素的下标。method: BFS
相邻的点之间有无向边相连，数值相同的点也有边相连，问题转化为求无向无权图的最短路问题，用BFS求解
BFS求解特点：先更新的节点一定拥有更短的路径，不需要再次更新，所以第一次碰到一个值的时候，就把相同值的点的最短路更新了，后面就不用再更新了，可以用used数组来标记是否更新过
数值相同的节点下标可以用哈希表存储
int minJumps(vector<int>& arr) {
unordered_map<int, vector<int>> mp;
int n = arr.size();
for (int i = 0; i < n; i++) {
mp[arr[i]].push_back(i); // 存储数值相同的值的下标
}
queue<int> q;
vector<bool> used(n);
q.push(0);
int depth = 0;
while (!q.empty()) {
int size = q.size();
while (size--) {
int index = q.front();
q.pop();
if (index == n - 1) return depth;
if (index - 1 >= 0 && !used[index - 1]) { // 往前跳一步
used[index - 1] = true;
q.push(index - 1);
}
if (index + 1 < n && !used[index + 1]) { // 往后跳一步
used[index + 1] = true;
q.push(index + 1);
}
for (auto m : mp[arr[index]]) {
if (!used[m]) {
used[m] = true;
q.push(m);
}
}
mp.erase(arr[index]); // 更新完就可以删掉了
}
depth++;
}
return depth;
}时间复杂度：$O(n)$，一个点最多入队一次
空间复杂度：$O(n)$，队列最多存储n个元素，哈希表最多有n个元素，一个vector里面最多有n个元素
