前端野人

我是Louis,自詡為野生的前端工程師,在網路中求生存

30Day LeetCoding Callenge — Week4

發布於
Photo by Guido Hofmann on Unsplash


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

喜歡我的文章嗎?
別忘了給點支持與讚賞,讓我知道創作的路上有你陪伴。

看不過癮?

一鍵登入,即可加入全球最優質中文創作社區