630. Course Schedule III
題目網址：https://leetcode.cn/problems/course-schedule-iii/
題意：有 n 個不同的課程, 編號從 1 到 n。給一整數 array course, 其中 courses[i] = [duration_i, lastDay_i] 代表第 i 門課程會持續 duration_i 天, 且須在 lastDay_i 之前完成。
學期從第 1 天開始, 且不得同時修習兩門(含)以上的課程。
返回最多可修習的課程數目。
Solution：
想法：利用 Greedy + Heap, 由於我們希望能修習的課越多越好, 因此我們要先將課程根據 deadline 由小到大排序, 因為 deadline 越是緊急的課越應該優先完成, 完成後才接著去安排 deadline 相對寬鬆的課
將所有課程根據 deadline 由小到大排序
用 max heap q 維護目前取的課程中 duration 最長的課
按照 deadline 的順序, 一一嘗試加入課程。一旦有課程無法在 deadline 前完成, 則取消掉目前取的課程中 duration 最長的課 ...
895. Maximum Frequency Stack
題目網址：https://leetcode.cn/problems/maximum-frequency-stack/
題意：設計一個類似 stack 的資料結構, 將元素 push 到 stack 中, 並從 stack 中 pop 出頻率最高的元素。
請實現 FreqStack class：
FreqStack()：建立一個空的 stack
void push(int val)：將整數 val push 到 stack 中
int pop()：刪除並返回 stack 中頻率最高的元素
若頻率最高的元素不只一個, 則刪除並返回最接近 stack top 的元素
Solution 1：
想法：利用 Bucket, 使用多個 stack, 來模擬 FreqStack。每 push 一個元素就要 push 到當前對應頻率的 stack 中。同一頻率中, 越晚加入的元素就會越接近其對應頻率的 stack 之 top
e.g. push [5, 7, 5, 7, 4, 5], 最後可得到下圖中右下角的表格, 然後依序從 freq 高的開始 pop ➔ pop 的順序由下往上、由右至 ...
480. Sliding Window Median
題目網址：https://leetcode.cn/problems/sliding-window-median
題意：中位數是指有序 array 裡中間的數。若 array 長度偶數, 則中位數是中間兩數的平均值。
arr = [2,3,4], 則中位數 = 3
arr = [2,3], 則中位數 = (2+3) / 2 = 2.5
給一整數 array nums 和一整數 k, 有一長度為 k 的 sliding window 從 nums 最左端滑到最右端, 每次向右移動一位, 求每次移動 sliding window 後得到的中位數, 並返回由這些中位數所組成的 array。
Solution：
想法：利用 Heap, 類似 295. Find Median from Data Stream, 使用兩個 heap + 延遲刪除, 我們定義平衡：
滿足 smaller.size() - larger.size() ≤ 1
也就是說 smaller 的元素個數要麼比 larger 多一, 要麼相同
這樣設計的好處在於：
當 k 為偶數時, 各自的 ...
745. Prefix and Suffix Search
題目網址：https://leetcode.cn/problems/prefix-and-suffix-search/
題意：設計一個可以透過 prefix 和 suffix 來搜尋單字的特殊字典。
請實現 WordFilter class：
WordFilter(string[] words)：使用 word 來初始化 WordFilter
f(string pref, string suff)：返回字典中具有前綴 prefix 和後綴 suffix 單字的 index。若不只一個 index 滿足要求, 則返回最大的 index。若不存在這樣的單字, 則返回 1。
其中, words[i]、pref、suff 僅由小寫字母所組成。
Solution 1：
想法：利用 hash table 去儲存每個單字所有可能的 prefix_suffix 組合, 並對應到該單字的 index。若有單字有相同的 prefix_suffix 組合, 則後面的單字會覆蓋掉前面的單字之 index
紀錄該單字的 prefixes、suffixes 長度為 n + 1, 其中 n 為該單字的長 ...
472. Concatenated Words
題目網址：https://leetcode.cn/problems/concatenated-words/
題意：給一 string array words (沒有重複單字), 找出並返回 words 中所有的連接詞。
連接詞：一個完全由 words 中至少兩個單字所組成的 string。
Solution 1：
想法：利用 DFS + Trie, 同 139. Word Break, 先對 words 根據 string 的長度進行排序, 因為排序後 word[i] 只會由比它短的單字所組成, 因此我們先把較短的單字 insert 到 trie 中後, 再來搜尋 word[i] 是否能由 trie 中的單字所組成
class TrieNode{public: TrieNode* children[26] = {nullptr}; bool isEnd = false;};class Trie{public: TrieNode *root; Trie() : root(new TrieNode()) &# ...