703. Kth Largest Element in a Stream
題目網址：https://leetcode.cn/problems/kth-largest-element-in-a-stream/
題意：設計一個找到 stream 中第 k 大的元素。注意是排序後的第 k 大元素, 而非第 k 個不同的元素。
實現 KthLargest class：
KthLargest(int k, int[] nums)：使用 k 和 nums 來初始化 instance
int add(int val)：將 val 加入倒 nums 中, 並返回第 k 大的元素
Solution：
想法：利用 Heap, 使用 min heap pq 來記錄前 k 大的元素, 其中 pq.top() 代表當前第 k 大的元素
KthLargest(k, nums)：先 push nums[i], 然後確認 pq.size() 是否 > k。若是的話, 則把 pq.top() 給 pop 掉, 讓 pq 的元素個數維持在 k 個
add(val)：先 push val, 然後確認 pq.size() 是否 > k。若是的話, 則把 pq.top() 給 ...
1065. Index Pairs of a String
題目網址：https://leetcode.cn/problems/index-pairs-of-a-string/
題意：給一 string text 和 string list words, 求所有 index pair 使得 text[i~j] 出現在 words 中。
Solution 1：
想法：暴力搜尋法
class Solution {public: vector<vector<int>> indexPairs(string text, vector<string>& words) { const int m = text.size(); vector<vector<int>> res; unordered_set<string> wordSet(words.begin(), words.end()); for (int start = 0; start < m; ++start) { ...
226. Invert Binary Tree
題目網址：https://leetcode.cn/problems/invert-binary-tree/
題意：給一 BT, 反轉其左右子樹。
Solution 1：
想法：利用 DFS
class Solution {public: TreeNode* invertTree(TreeNode* root) { if (!root) { return root; } swap(root->left, root->right); invertTree(root->left); invertTree(root->right); return root; }};
time：$O(n)$ ➔ 遍歷整個 BT
space：$O(n)$ ➔ worse case：skew tree, 遞迴深度為 n
Solution 2：
想法：利用 BFS
class Solution ...
1046. Last Stone Weight
題目網址：https://leetcode.cn/problems/last-stone-weight/
題意：給一整數 array stones, 其中 stones[i] 代表第 i 塊石頭的重量。
每一回合取出最重的兩塊石頭, 並將其互相撞擊。假設石頭的重量分別為 x、y, 且 x ≤ y。則撞擊後的可能結果如下：
若 x == y, 則兩塊石頭都將完全粉碎
若 x != y, 則重量為 x 的石頭將完全粉碎, 而重量為 y 的石頭之新重量為 y - x
最後, 頂多剩下一塊石頭。若沒有石頭剩下, 則返回 0; 否則, 返回該石頭的重量。
Solution：
想法：利用 Heap, 先將所有的元素 push 到 max heap pq 中, 再從 pq 中兩兩取出元素做運算
class Solution {public: int lastStoneWeight(vector<int>& stones) { priority_queue<int> pq; // max heap for ...
141. Linked List Cycle
題目網址：https://leetcode.cn/problems/linked-list-cycle/
題意：判斷 linked list 中是否有 cycle。
Solution：
想法：利用兩個不同步長的 ptr, slow 每次只走一步, 而 fast 每次走兩步
若存在循環, 則 slow 和 fast 必相遇（fast 倒追 slow）
若不存在循環, fast 必先抵達 nullptr
class Solution {public: bool hasCycle(ListNode *head) { ListNode *slow = head, *fast = head; // 判斷 fast, 因為若沒有 cycle, fast 會比較快抵達 nullptr while ( fast && fast->next) { slow = slow->next; // 一次走一步 fast = fast->next ...