一、思路：

? ? 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 给定一个非负整数数组，你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 你的目标是使用最少的跳跃次数到达数组的最后的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。