文章目錄
- 貪心演算法
- 跳躍游戲 I
- 思路分析
- 代碼實作
- 跳躍游戲 II
- 思路
貪心演算法
貪心演算法可以理解為一種特殊的動態規劃為題，擁有一些更加特殊的性質，可以進一步降低動態規劃演算法的時間復雜度，
來看幾道題目熟悉一下這種“不斷尋求區域最優”的演算法，
跳躍游戲 I
輸入一個非負整數陣列nums，陣列元素nums[i]表示的是：如果你站在位置 i ，最多能夠往前跳幾步，
現在你站在第一個位置nums[0]，試問你能否跳到陣列的最后一個位置?
例：[1,2,3,4,5]，可以
[1,2,0,0,4]，不行
思路分析
這題相對比較簡單一些吧，當然不要去用回溯，用回溯的話時間復雜度太高，
成功的方式太多了，但是失敗的方式只有一個：有足夠多的0橫亙在其中，導致不論怎么努力就是跳不過去，
我們哪幾個栗子來試一下吧：
[0,····] //點點點的意思是隨便你填什么數字都無所謂了
[1,2,1,0,···]
[2,0,0,···]
//還有啥特例嗎？
我們來分析一下上面的栗子（我們假設陣列有-1格，nums[-1] = 1，我們從nums[-1]開始）：
第一個栗子：在下標為0的時候遇到了絕望的0，從下標為-1的地方為此前能前進的最大步數1，無法跨越，終結，
第二個栗子：在下標為3的時候遇到了絕望的0，從下標為1的地方獲得了此前能前進的最大步數2，無法跨越，失敗，
第三個栗子：在下標為2的時候遇到了絕望的0，從下標為0的地方獲得了此前能前進的最大步數2，無法跨越，失敗，
這三個栗子中，我們能提取出什么有效的資訊？
0 -（-1） = 1
3 - 1 = 2
2 - 0 = 2
對吧，
還有呢？為什么不變通一下，比如說例2中，不通過下標為2的點去中轉呢？因為中轉也無效啊，
那就是說我們要去嘗試著中轉，
這樣講可能會有點繞啊，我把例2改一下：[1,2,2,0]，這不就活了嗎！
拿兩個例2來比對一下：
（以flag紀錄當前能夠到達的最遠距離）
[1,2,1,0,···]
//下標0最多到下標1，flag = 1；下標1最多到下標3，flag = 3；下標2最多到下標3，flag = 3；下標3，flag = 3；卒
[1,2,2,0]
//下標0：flag = 1；下標1：flag = 3；下標2：flag = 4
可以看到，當flag == 下標 的時候，就涼涼了，
代碼實作
所以，我們寫出代碼：
bool canJump(vector<int>& nums){
int n = nums.size();
int farthest = 0;
for(int i = 0; i < n-1; i++){
//不斷計算能夠跳到的最遠距離
farthest = max(farthest,i+nums[i]);
//如果碰到0跳不動了
if(farthest <= i) return false;
}
return farthest >= n-1;
}
跳躍游戲 II
跟上面差不多，但是這次保證你能跳到最后，問你最少跳幾次，
看著好眼熟啊，好像前面寫過一道這樣的題，換硬幣是吧，
去遞回選取后續跳法里面的最優，屬于一種：從后向前的解法，可以理解為從底層開始層序遍歷一棵樹，只不過我們后來通過備忘錄對這棵樹進行了剪枝，不然真的不忍直視啊，
但是呢，我們今天講的是貪心演算法，它可以想象成從上往下一條路走下去，讓我們看看：
思路
貪心演算法是什么？貪心演算法會選擇當下最有潛力的一步，
舉個例子：[2,3,1,2,5,1]
當你現在在下標0的位置，你可以跳兩步，動歸的話會遞回去算這兩步到最終結果的最優步數，但是貪心演算法不這樣，
貪心演算法是每次盡可能多跳嗎？NoNoNo，選擇當下最有潛力的：在坐標1的位置，你有三個選擇；在坐標2的位置，你只有一個選擇，所以貪心演算法會讓你選擇跳到坐標1，這就是貪心演算法的區域最優（不要奇思妙想啥反例，要用貪心演算法，就要承擔它的失誤率），
接下來，我們來寫代碼：
int jump(vector<int>& nums){
int n = nums.size();
//站在索引i，最多能跳到索引end
int end = 0;
//從索引【i···end】起跳，最遠能到的距離
int farthest = 0;
//紀錄跳躍次數
int jumps = 0;
for(int i = 0; i<n; i++){
farthest = max(nums[i]+1,farthest);
if(end == i){
jumps++;
end = farthest;
}
}
return jumps;
}
右手中指都麻了，，
歇了歇了，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/264226.html
標籤：其他
上一篇：PID控制的理解與具體實作
下一篇：2. 洗掉最大和最小