30Day LeetCoding Callenge — Week4

第四週，所使用的技巧為前三週總合，但題目思維更加的抽象，總之就是驗證你是否真正了解怎麼應用所學技巧，這次介紹兩個演算法(algorithm)

1. Backtracking
2. 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
};

更多解題詳解：https://ithelp.ithome.com.tw/articles/10231333