LeetCode 45. Jump Game II

题意

有 n 个点，每个点有从这个点最多能前进的距离，求从第一个点到最后一个点的最少步数

思路

首先应该想到搜索，但是DFS太耗时，所以想到 BFS ，但是如果按照距离来进行搜索，可能还是会超时，所以说要使用其他方法，可以发现，选择的落脚点必然是越靠近终点越好，所以设置三个变量：

maxLoc ：当前选择的落脚点能到达的最远处 maxPos ：当前遍历点能到达的最远处 ans ：记录当前已走的步数

在遍历过程中更新 maxPos ，当遍历点到达 maxLoc 的时候，更新步数和 maxLoc ，同时初始化 maxPos ，以便后面的更新.

代码

class Solution { public: int jump(vector<int>& nums) { size_t len = nums.size(); int maxLoc = 0, maxPos = 0, ans = 0; for(int i = 0; i < len; i++){ if(maxLoc >= len - 1) break; maxPos = max(maxPos, i + nums[i]); if(i == maxLoc){ ans++; maxLoc = maxPos; maxPos = -1; } } return ans; } };