IPFS 指纹 这是什么
30Day LeetCoding Callenge — Week4
第四週，所使用的技巧為前三週總合，但題目思維更加的抽象，總之就是驗證你是否真正了解怎麼應用所學技巧，這次介紹兩個演算法(algorithm)
- Backtracking
- Greedy
Backtracking
回朔法常用於找出任何可能解的答案。如排列組合。
請問ABC 三個字母最多有幾種不重複字母的排列組合？
Lecture 10 | Programming Abstractions (Stanford)
JumpGame 有一解就是使用 BackTracing，從程式碼結構看會發現跟上面的字母排序的結構很像，判斷式，下面有個迴圈處理遞迴，Backtracking 在我的理解就是 Recursion 的進階用法，而迴圈會因為判斷問題最來越小，最後停止。
var canJump = function(nums) {
const canJumpFormPosition = (position, nums) => {
if(position == nums.length -1 ){
return true
}
const furthestJump = Math.min( position + nums[position] , nums.length -1)
for(let nextPosition = furthestJump ; nextPosition > position ; nextPosition --){
if(canJumpFormPosition(nextPosition ,nums)) return true
}
return false
}
return canJumpFormPosition(0,nums)
};
Greedy
greedy 為貪婪演算法，greedy的特性就是 在執行當下就決定結果，greedy有一個經典題目可以供大家發想：換硬幣。
給一個金額，幣值1,5,10,50 請用最少硬幣數換兌金錢。這是最經典的greedy 題目，換硬幣的思維就是先除最大的然後再依序往下找能換得硬幣。
同樣是零錢換整問題, 如果可換硬幣的面額改成 25 元, 18 元, 5 元, 1 元, 則 greedy algorithm 所求出的就不是最佳解了。 例: n = 41, 用 greedy algorithm 解得 1 個 25 元, 0 個 18 元, 3 個 5 元, 1 個 1 元; 但最佳解其實是 0 個 25 元, 2 個 18 元, 1 個 5 元, 0 個 1 元。 (真的有學者 做類似的建議。) Q: 有沒有什麼規則可以看出 "零錢換整問題" 何時可以用 greedy algorithm? - 參考段落
上面是Greedy失敗的例子，如果面額更換後，就不能單純判斷大小換兌金額，雖然有致命缺點，但在合理的題目下Greedy仍然是最好的選擇之一。
如這次的Jump Game 最佳解就是使用Greedy，這個題目如果以直覺照題意設計的話，會是用BackTracking的方式去解，但是BackTracking 是找出任何解的組合，所以當數量太多的時候就容易over，這時就必須用Greedy去思考，因為題目最終只是要一個boolean，所以Greedy 時從最後一個 元素往回推 如果 索引值跟索引值內的元素相加會大於數組的長度，那就是正確的，而能到達當下索引值的其他元素也是正確的，就這樣回推到起點，Greedy不需要考慮能達到終點的組合，只要計算長度而已，所以速度上就快很多。
var canJump = function(nums) {
let lastInd = nums.length - 1
for(let i = lastInd ; i >= 0 ; i--){
if(i + nums[i] >= lastInd){
lastInd = i
}
}
return lastInd == 0
};