leetcode C++ 45. 跳跃游戏 II 给定一个非负整数数组，你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 你的目标是使用最少的跳跃次数到达数组的最后

一、思路：

    1、深度搜索，不剪枝，只能通过71多个

     2、深度搜索，map存储每一个pos的count,凡是后面超过这个count，停止搜索，剪枝，最后两个也通过不了

     3、O(n), 通过当前节点找到下下节点的最远位置，保存最远的下一个节点位置，继续这样遍历保存的这个节点，知道下下节点达到末尾。

二、代码：

class Solution { public:int jump(vector<int>& nums) {if (nums.size() < 2)return 0;int res = 0;int nowPos = 0;int maxPos = 1;while (maxPos < nums.size() - 1) {res += 1;maxPos = INT_MIN;int count = nums[nowPos];int tempNowPos = nowPos;while (count > 0) {int temp1 = tempNowPos + count;if (temp1 >= nums.size() - 1)return res;int pos = temp1 + nums[temp1];if (maxPos < pos) {maxPos = pos;nowPos = temp1;}count--;}}return res + 1;}};

 

总结

以上是生活随笔为你收集整理的leetcode C++ 45. 跳跃游戏 II 给定一个非负整数数组，你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 你的目标是使用最少的跳跃次数到达数组的最后的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。