LeetCode 45 Jump Game II

本文主要是介绍LeetCode 45 Jump Game II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

给出一个步长数组nums，如果一个人站在i这个点上那么他可以向右最多走nums[i]步，求从左端点走到右端点的最少步数。

思路：

如果点x可以用dp[x]步到达，那么[ x + 1, x + nums[x] ]区间内的点都可以用dp[x] + 1步到达。

利用这个想法，可以O(n)的求出走一步可以到达哪些位置，走两步可以到达哪些位置，以此类推。

代码：

class Solution {
public:int jump(vector<int> &nums) {int n = nums.size();if (n <= 1) {return 0;}int pos = 0, arr = 0;int cnt = 0;while (pos < n) {int next = 0;while (pos < n && pos <= arr) {next = max(pos + nums[pos], next);++pos;}arr = next;++cnt;}return cnt - 1;}
};

这篇关于LeetCode 45 Jump Game II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---