跳跃游戏

跳跃游戏 I跳跃游戏 II跳跃游戏 III跳跃游戏 IV跳跃游戏 V

跳跃游戏 I

https://leetcode-cn.com/problems/jump-game/

数组的下标表示位置的编号，数组中的元素表示我们可以从当前位置向后跳多远 可以采用贪心的策略，我们从前向后遍历一遍，对于每次遍历，需要维护一个变量 (之前可以到达的最远的位置)，max (ans, i + nums[i])。

只要发现当前位置比我们维护的可到达的最大位置大，那么就说明当前位置是无法到达的，直接返回false。

跳跃游戏 II

https://leetcode-cn.com/problems/jump-game-ii/

相对之前的题来说，这里要求我们使用最少的跳跃次数，从起点到终点(0 - n-1)。（这总是可以到达的）

使用深度优先搜索对所有结果进行模拟

对于每一个搜索，我们维护一个当前可到达终点的最小跳跃次数min_jump，当前可以到达的位置index，以及当前的跳跃次数now_jump

class Solution { public: int jump(vector<int>& nums) { int len = nums.size(); int min_jump = 0x0000ffff; dfs(nums,len,0,min_jump,0); return min_jump; } //深搜超时 [5,6,4,4,6,9,4,4,7,4,4,8,2,6,8,1,5,9,6,5,2,7,9,7,9,6,9,4,1,6,8,8,4,4,2,0,3,8,5] void dfs(vector<int>& nums, int& len, int index,int& min_jump,int now_jump) { //判断是否可以直接跳到最后一步 if(index >= len-1) { min_jump = min(min_jump,now_jump); return ; } for(int i = nums[index]; i > 0; i--) dfs(nums,len,index+i,min_jump,now_jump+1); } };

最后，这样直接暴力去搜索显然是超时的，他的时间复杂度也是比较高的。由于模拟的问题，我们做了很多重复的工作

动态规划

第二种就是可以用动态规划的思想，当我们从位置A 跳到位置B 时，位置B的最少跳跃次数就等于min (dp[B], dp[A] + 1)。要么我自己的之前维护的次数就是最小的，要么就是从0-A跳跃的次数 + 1

dp[i] ，表示从开始位置0到位置i，所需的最小跳跃次数。

class Solution { public: //动态规划 超时 int jump(vector<int>& nums) { int len = nums.size(); vector<int> dp(len,0x0000ffff);//dp[i]表示跳到当前位置最小跳跃次数 dp[0] = 0; for(int i = 0; i < len; i++) { int jump = min(len-1,i+nums[i]); // 可以向后跳jump个位置 for(int j = i; j <= jump; j++) { dp[j] = min(dp[j],dp[i]+1); } } return dp[len-1]; } };

由于双重遍历的原因，时间复杂度为O(n^2)。最终是卡在了一个逐级递减的数据集中

广度优先搜索

深度搜索是因为可以出现的情况很多，出现了很多重复搜索的情况，那么广度搜索可以解决这一问题

这里需要注意，我们每次维护一个是否被搜索过的数组visit，当我们在入队的时候，发现该位置是被搜索过的，也就是曾经出现在队列中，那么就放弃。

class Solution { public: //BFS int jump(vector<int>& nums) { int len = nums.size(); if(len < 2) return 0; vector<int> visit(len,0); queue<int> que; que.push(0);//开始点入队 visit[0] = 1; int ans = 0; while(!que.empty()) { int size = que.size(); for(int i = 0; i < size; i++) { int pos = que.front(); que.pop(); if(pos + nums[pos] >= len-1) return ++ans; for(int j = nums[pos]; ~j; j--) { if(visit[pos + j]) continue; que.push(pos + j); visit[pos + j] = 1; } } ans++; } return -1; } };

还需要注意的一点就是，在元素入队的时候，我们需要从后向前判断，从可以跳的最远的位置到最近的位置来入队，如果发现某个位置判断过，及时continue（no break）

贪心

在贪心的策略中，我们只需要遍历一次整个数据集，那么就可以得到一个结果。

可以说是一个简化版的广度优先搜索

class Solution { public: //每一次遍历就找当前可以到的最远的距离进行比较 int jump(vector<int>& nums){ int end = 0; //记录上一次可以调到的位置 int maxPos = 0; //记录当前最远可以跳到的位置 int ans = 0; //跳的次数 //当i到了最后一个位置就表示成功了，就不需要再跳了 for(int i = 0; i < nums.size()-1; i++) { maxPos = max(maxPos,nums[i] + i); if(i == end)//需要更新最后的位置了 { end = maxPos; ans++; } } return ans; } };

跳跃游戏 III

https://leetcode-cn.com/problems/jump-game-iii/

相比前面的问题，在每一个位置时，只能跳到他的左边i + arr[i]或者他的右边i - arr[i]。

所以我们就可以从start 位置开始，以广度遍历的方式对每次队列中的位置进行一次更新，在更新可到达位置的时候，需要注意判断数据范围是否越界。

class Solution { public: bool canReach(vector<int>& arr, int start) { int n = arr.size(); vector<bool> vis(n,false); queue<int> que({start}); vis[start] = true; while ( que.empty() == false ) { int size = que.size(); while ( size -- ) { int f = que.front(); que.pop(); if(arr[f] == 0) return true; // i + arr[i] int pos = f + arr[f]; if(pos < n && vis[pos] == false) { que.push(pos); vis[pos] = true; } // i - arr[i] pos = f - arr[f]; if( pos >= 0 && vis[pos] == false) { que.push(pos); vis[pos] = true; } } } return false; } };

跳跃游戏 IV

https://leetcode-cn.com/problems/jump-game-iv/

和跳跃III相比，对于每一个位置可以到达的地方，多了一个可以向和当前数据相同，但是位置不同的地方跳跃的条件；同时，对于左右跳跃，也只能跳到相邻并且合法的位置

注意三个点：

离散化数据集。对于 1 7 7 7 7 7 7 11 这样的数据，可以缩小他的范围，离散化为1 7 7 11。因为我们的目标都是到达终点，减少不必要的开支维护一个有向图。对于每一个位置，我们在开始之前就需要知道他可以跳到那些地方动态规划。 dp[i]，表示从 0 - i，所需要的最小跳跃次数。那么对于 dp[j]，他的最小跳跃次数就是 min (dp[j], dp[i] + 1) class Solution { public: int minJumps(vector<int>& arr) { int n = arr.size(); // 离散化 1 7 7 7 7 11 --》 1 7 7 11 int m = 0; for(int i = 0; i < n; i++) { int len = 1; while(i + len < n && arr[i] == arr[len + i]) len++; arr[m++] = arr[i]; if(len != 1) arr[m++] = arr[i]; i += len - 1; } queue<int> que({0}); int dp[m]; memset(dp,0x3f,sizeof(dp)); dp[0] = 0; // 有向图 unordered_map<int,set<int> > ums; for(int i = 0; i < m; i++) ums[arr[i]].insert(i); int ans = 0; while (que.empty() == false) { int size = que.size(); while (size --) { int f = que.front(); que.pop(); if(f == m - 1) return ans; // 当前位置为终点 // left int le = f - 1; if(le >= 0 && dp[le] > dp[f] + 1) { que.push(le); dp[le] = dp[f] + 1; } // right int ri = f + 1; if ( ri < m && dp[ri] > dp[f] + 1) { que.push(ri); dp[ri] = dp[f] + 1; } // same for ( auto& index : ums[arr[f]] ) { if(dp[index] > dp[f] + 1) { que.push(index); dp[index] = dp[f] + 1; } } } ans++; } return -1; // 无法跳到终点 } };

跳跃游戏 V

https://leetcode-cn.com/problems/jump-game-v/

对于这个问题来说，每个位置代表一个有高度的柱子，人在柱子上，每一次我们可以向左，或者向右进行跳跃，但是只能跳到比当前高度低的一个柱子上

注意：

升序排列。先把所有的柱子按照升序进行排列，同时注意数组的每个节点都是一个pair类型的结构体，其中的两个元素分别是柱子的下标以及高度。动态规划。 dp[i]，表示从 0 - i，所需要的最小跳跃次数。那么对于 dp[j]，他的最小跳跃次数就是 min (dp[j], dp[i] + 1)遍历。每次遍历都已当前idx位置为中心，依次向两边进行遍历。遇到边界问题或者高度问题，就直接跳过

在遍历时，由于我们是按照柱子的升序进行遍历的，又因为每次只能向比自己低的地方进行跳跃，所以我们就可以确定出每次min (dp[j], dp[i] + 1)时，对于dp[i]总是我们已经计算好的一个结果。

class Solution { public: int maxJumps(vector<int>& arr, int d) { int n = arr.size(); vector<int> dp(n,1); vector<pair<int,int> > index(n); for(int i = 0; i < n; i++) index[i] = {i,arr[i]}; // 按照每个位置的高度，进行升序排列 sort(index.begin(),index.end(),[](const pair<int,int>& a,const pair<int,int>& b)->bool{ return a.second < b.second; }); int ans = 0; for(int i = 0; i < n; i++) { int idx = index[i].first; // idx -> for(int j = 1; j <= d; j++) { int pos = idx + j; if(pos >= n || arr[pos] >= arr[idx]) break; dp[idx] = max(dp[idx],dp[pos] + 1); } // <- idx for(int j = 1; j <= d; j++) { int pos = idx - j; if(pos < 0 || arr[pos] >= arr[idx]) break; dp[idx] = max(dp[idx],dp[pos] + 1); } ans = max(ans,dp[idx]); } return ans; } };