Greedy
LeetCode 763: Partition Labels
·1 分鐘
LeetCode
Medium
Hash-Table
Two-Pointers
String
Greedy
LeetCode 763 解題筆記:先記每個字母最後出現的位置,掃描時把這段的結尾延伸到最遠,走到結尾就切
LeetCode 452: Minimum Number of Arrows to Burst Balloons
·1 分鐘
LeetCode
Medium
Array
Greedy
Sorting
LeetCode 452 解題筆記:按右端點排序,箭射在右端點,左端點大於箭的位置才需要新的一支;端點相接算重疊
LeetCode 4099: Minimum Operations to Sort With Locked Indices
·2 分鐘
LeetCode
Medium
Array
Merge-Sort
Greedy
LeetCode 4099 解題筆記:交換次數就是逆序數;有元素要跨過的上鎖位置一定要解鎖,數出來和 k 比,加上 merge sort 算的逆序數
LeetCode 4098: Minimize the Maximum Value of GCD-Connected Array
·2 分鐘
LeetCode
Medium
Math
Number-Theory
Greedy
LeetCode 4098 解題筆記:value 的最小質因數 p 決定一切:後一個最小是 value + p,之後都是偶數每次加 2;左邊可行的條件是 value - p >= 2 * index
Stack 與單調棧
·3 分鐘
演算法
Stack
Monotonic-Stack
Greedy
Simulation
巢狀結構解析、跟前一個元素合併的模擬、單調棧、貪心刪字元取字典序最小,以及 lazy deletion 的 Max Stack
Heap 優先佇列
·3 分鐘
演算法
Heap
Priority-Queue
Greedy
Dijkstra
heapq 基本用法、Top-K、lazy deletion、雙 heap、K 路合併、掃描線與 Dijkstra
Greedy 貪心
·4 分鐘
演算法
Greedy
Sorting
Intervals
排序後掃描、區間按右端點排序、左右兩次掃描、配對與奇偶不變量、相鄰差值,以及「比平均大的先拿掉」;每一種都附上為什麼貪心是對的
LeetCode 4045: Count Robot Groups
·1 分鐘
LeetCode
Medium
Stack
Monotonic-Stack
Greedy
LeetCode 4045 解題筆記:先合併 t = 0 就夠近的機器人,再從右往左像車隊一樣,比前面車隊快的遲早會併入
LeetCode 2561: Rearranging Fruits
·1 分鐘
LeetCode
Hard
Greedy
Hash-Table
Sorting
LeetCode 2561 解題筆記:每種值總數要是偶數;多出來的排序後,便宜的一半各自跟貴的交換,成本取 min(便宜的值, 2 × 全域最小值)
LeetCode 1354: Construct Target Array With Multiple Sums
·1 分鐘
LeetCode
Hard
Heap
Math
Greedy
LeetCode 1354 解題筆記:反著做,最大值一定是最後被設定的;差距大時用取餘數一次跳完
LeetCode 420: Strong Password Checker
·2 分鐘
LeetCode
Hard
Greedy
String
LeetCode 420 解題筆記:分長度三種情況,太長時優先刪除 len % 3 == 0 的重複段來抵銷取代次數
LeetCode 2193: Minimum Number of Moves to Make Palindrome
·1 分鐘
LeetCode
Hard
Two-Pointers
Greedy
String
Binary-Indexed-Tree
LeetCode 2193 解題筆記:貪心處理最外層:拿最後一個字元,把它最左邊的同伴換到最前面,花費是那個位置;落單的字元最後在正中間,花費是它到中間的距離