演算法 · 5 個細項
Greedy貪婪法
貪婪法不回頭、不試錯,只做眼前最好的選擇,所以通常最快。代價是它不一定對:這個主題的重點不只是寫出貪婪解,而是學會用交換論證判斷什麼時候可以貪。
為什麼要學 Greedy
現實中的應用細項
5 篇#演算法複雜度難度狀態
01Greedy Principles 貪婪正確性貪婪選擇性質、交換論證用在:判斷一題能不能貪,不能就轉 DP—空間 —可學習02Coin Change (Greedy) 找零問題標準幣值可以貪,任意幣值會錯用在:收銀找零、理解貪婪何時會失敗O(n)空間 O(1)可學習03Interval Scheduling 區間排程按結束時間排序,Merge Intervals、Meeting Rooms用在:會議室安排、CPU 工作排程、廣告時段O(n log n)空間 O(1)可學習04Jump Game 跳躍遊戲維護最遠可達位置用在:資源夠不夠到達目標的快速判斷O(n)空間 O(1)可學習05Huffman Coding 霍夫曼編碼用堆積每次合併最小的兩個頻率用在:zip、JPEG、MP3 的熵編碼階段O(n log n)空間 O(n)可學習