451. Sort Characters By Frequency
題目網址：https://leetcode.cn/problems/sort-characters-by-frequency/
題意：給一 string s, 根據每個 char 出現的頻率對其進行降序排列。
返回已排序過的 string, 若有多個答案, 則返回其中任意一個。
Solution：
想法：利用 Heap
計算 s 中每個元素的出現頻率
將 {char, cnt} push 到 max heap 中
不斷取出 top 直到 heap 為空, s.append(cnt, char) 代表 s 一次新增 cnt 個 char
class Solution {public: string frequencySort(string s) { unordered_map<char, int> freq; priority_queue<pair<int, char>> q; // max heap for (const auto& ch : ...
310. Minimum Height Trees
題目網址：https://leetcode.cn/problems/minimum-height-trees/
題意：給一數字 n 和 n - 1 條無向邊的 edges list, 代表一包含 n 個 node 編號從 0 到 n - 1 的 tree。
可選擇 tree 中任意 node 作為 root。在所有可能的 tree 中, 具有最小高度的 tree 被稱為最小高度樹。
找到所有最小高度樹的 root 並按任意順序返回。
Solution 1：
想法：利用 Topological Sort + BFS, 我們發現若希望高度越小, 則 root 應選 degree 越大的。
下圖中, 紅圈以外的是 leaf, 若將這些點作為 root, 其樹高不可能為最小的, 原因如下:
若將 leaf 作為 root, 其樹高的路徑必「走進」紅圈, 再「走出」紅圈
若將 non-leaf 為 root, 其樹高的路徑只需「走出」紅圈
➔ 故可透過「剝洋蔥」的方式, 一層一層剝掉 degree = 1 的 node, 直到剩下 ≤ 兩個 node。
思考: 為 ...
444. Sequence Reconstruction
題目網址：https://leetcode.cn/problems/sequence-reconstruction/
題意：給一 [1, n] 長度為 n 的整數 array nums, 以及一些 2d 整數 array sequences, 其中 sequences[i] 是 nums 的 subsequence。
返回 sequences 是否能唯一重建出 nums。
e.g. nums = [1,2,3], sequences = [[1,2], [1,3]]
sequences 可重建出 [1,2,3] 和 [1,3,2] 並不唯一, 故返回 false。因為 1 必須在 2、3 的前面, 但 2 和 3 間並沒有唯一的順序
但若更改 sequences = [[1,2], [1,3], [2,3]], 則可唯一重建出 [1,2,3], 故返回 true。因為 1 必須在 2、3 的前面, 且 2 必須在 3 的前面, 故只能重建出 [1,2,3]
Solution：
想法：利用 Topological Sort + BFS, 將 sequences 轉成有向圖, 給 ...
107. Binary Tree Level Order Traversal II
題目網址：https://leetcode.cn/problems/binary-tree-level-order-traversal-ii/
題意：給一 BT 的 root, 返回 node.val 由下往上的 level order（由下層往上層, 每層由左至右）。
Solution 1：
想法：利用 BFS, 同 102. Binary Tree Level Order Traversal, 只是多了 reverse
class Solution {public: vector<vector<int>> levelOrderBottom(TreeNode* root) { if (!root) { return {}; } vector<vector<int>> res; queue<TreeNode*> q; q.emplace(root); ...
103. Binary Tree Zigzag Level Order Traversal
題目網址：https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/
題意：給一 BT 的 root, 返回 node.val 的 zigzag（鋸齒形）level order（先從左往右, 而下一層從右往左遍歷, 依此類推, 層與層之間交替進行）。
Solution 1：
想法：利用 BFS
class Solution {public: vector<vector<int>> zigzagLevelOrder(TreeNode* root) { if (!root) { return {}; } int depth = 0; vector<vector<int>> res; queue<TreeNode*> q; q.emplace(root); w ...