Jump Game II

原題鏈接Jump Game II

給定一個數組序列，序列中每一個元素的值表示最多可以向后跳多遠，初始時從下標0開始，計算最少跳多少次可以到達末尾的元素位置。

剛開始是想用深度優先（dfs）+ 動態規劃解決的，結果竟然超時了，看到答案后真是….哎╮(╯▽╰)╭

---

對于每個位置，它跳一次可以到達的位置是一個范圍，而對于這個范圍，跳一次可以到達的位置仍然是一個范圍。以示例序列[2,3,1,1,4]為例。
初始時，在下標為0的位置上，可以到達的下標范圍是[1,2]
對于下標1，可以到達的下標范圍是[2,4]。對于下標2，可以到達的下標范圍是[3,4]。所以范圍[1,2]可以到達的范圍是[3,4]。

所以如果每次移動的都是一個范圍，那么直到這個范圍包含最后一個位置，就說明已經到達末尾了。而移動的次數，就是移動范圍的次數。
代碼如下

class Solution { public:int jump(vector<int>& nums) {int n = nums.size();int steps = 0;/* [start, end]記錄當前達到的范圍，初始為0 */int start = 0;int end = 0;while(end < n - 1){/* 找下次可以到達的最遠位置 */int max_pos = 0;for(int i = start; i <= end; ++i)max_pos = std::max(max_pos, i + nums[i]);/* 對于可以到達最遠位置的那個下標i，它可以到達的位置為[i+1, max_pos]，即* start, ..., i, i+1, i+2, end, ... ,max_pos* 下次的范圍就是[end + 1, max_pos] */start = end + 1;end = max_pos;++steps;}return steps;} };

---

Jump Game

原題鏈接 Jump Game

這個就是判斷能不能到達最右邊，方法和上面一樣，轉換為廣度優先解決
代碼如下

class Solution { public:bool canJump(vector<int>& nums) {int left = 0;int right = 0;while(right < nums.size() - 1){int max_pos = right;for(int i = left; i <= right; ++i)max_pos = std::max(max_pos, nums[i] + i);if(max_pos <= right)return false;left = right;right = max_pos;}return true;} };

---

上面兩道題主要是將題目轉換為廣度優先（bfs）進行解決。因為每個位置可以達到的位置都是一個范圍，那么就導致不確定應該將它跳到哪，從而會有很多中可能，深度優先是依次考慮每種可能，會比較慢。而廣度優先將所有的可能一起考慮，每次都移動一個范圍，從而不需要那么多的迭代（遞歸）次數。

總結

以上是生活随笔為你收集整理的每天一道LeetCode-----数组序列，每个元素的值表示最多可以向后跳多远，计算最少跳多少次可以到达末尾的全部內容，希望文章能夠幫你解決所遇到的問題。

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