138. Copy List with Random Pointer
題目網址：https://leetcode.cn/problems/copy-list-with-random-pointer/
題意：給一長度為 n 的 linked list, 每個節點包含一個額外增加的隨機 pointer random, 該 pointer 可以指向 linked list 中的任何節點 or 空節點。
建構該 linked list 的 deep copy, 它由 n 個新節點組成, 其中每個新節點的值都設為其對應的 node.val。
新節點的 next 和 random 也都應指向新 linked list 中的其他節點, 使原 linked list 和新 linked list 能夠表示成相同的 linked list。
e.g. 如果原 linked list 中有 X 和 Y 兩個節點, 其中 X.random --> Y。則新 linked list 中對應的兩個節點 x 和 y, 同樣有 x.random --> y。
返回新 linked list 的 head。
Solution 1：
想法：利用 hash table, ...
2. Add Two Numbers
題目網址：https://leetcode.cn/problems/add-two-numbers/
題意：給兩個非空 linked list 表示兩個非負整數, 每位數字都是按照逆序（e.g. 個位數在前, 十位數在後）儲存的, 且每一個 node 只能存一位數字。請將兩數相加, 並以相同型式返回和的 linked list。
除了數字 0 以外, 其他數字都不會以 0 作為開頭。
Solution：
想法：用 dummy 記住新的 linked list 開頭, tail 用來更新新的 linked list 之尾端。除此之外, 還要考慮進位(carry bit)和以下特殊情況：
兩個整數長度不一（e.g. 123 + 4567）➔ 當 node 為 NULL 時, 把 node->val 設為 0
進位導致輸出比原本最長整數還長（e.g. 1 + 99 = 100）➔ loop 終止條件須判斷 carry bit 是否為 0
class Solution {public: ListNode* addTwoNumbers(Li ...
287. Find the Duplicate Number
題目網址：https://leetcode.cn/problems/find-the-duplicate-number/
題意：給一有 n + 1 個數的 array nums, 每個元素值皆在 [1, n], 剛好只有一數字重複, 求重複的數字。
注意：只能使用 $O(1)$ space, 且不能改變 nums
進階：設計 $O(n)$ time 的演算法
Solution 1：
想法：利用 Binary Search, 先在 [1, n] 中找中點 mid, 然後判斷整個 nums 中 ≤ mid 的元素個數 cnt。若 cnt > mid 代表有重複, 則往左繼續找
不要考慮 nums, 只需要考慮數字都在 1 到 n 之間nums = [1,3,4,2,2] 此時數字在 1 到 4 之間mid = (1 + 4) / 2 = 2, nums 中 ≤ 2 的有3個(1,2,2), 1到2中肯定有重複, 往左搜尋 ➔ right = 2mid = (1 + 2) / 2 = 1, nums 中 ≤ 1 的有1個(1), 2到2中肯定有重複, 往右搜尋➔ left = 2 ...
146. LRU Cache
題目網址：https://leetcode.cn/problems/lru-cache/
題意：設計並實現一個滿足 LRU（Least Recently Used）的資料結構。
實現 LRUCache class：
LRUCache(int capacity)：以 capacity 初始化 LRU cache 的大小。
int get(int key)：若 key 存在於 cache 中, 則返回其對應的 val, 否則返回 1。
void put(int key, int value)：
若 key 已經存在, 則變更其 value
若不存在, 則將該組 key-value insert 到 cache 中
若 insert 操作導致 pair 數量超過 capacity, 則移除最久未使用的 key-value pair
注意：get() 和 put() 必須是 $O(1)$ time
Solution：
想法：利用 hash table + list, 其中 cache 用來存放所有的 key, 用來記錄哪個 key 最近被使用、最久沒被使用。用 list 而非 f ...
235. Lowest Common Ancestor of a Binary Search Tree
題目網址：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/
題意：給一 BT 和兩個節點 p, q, 求兩節點之最低共同祖先(LCA)
Solution：
想法：利用 DFS 和 BST 的性質, 找到一 node 滿足 node.val 介於 p、q 之間
p->val ≤ node.val ≤ q->val 或
q->val ≤ node.val ≤ p->val
BST 性質:
root 左子樹中所有 node.val 皆小於 root.val
root 右子樹中所有 node.val 皆大於 root.val
class Solution {public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if (p->val > root->val && q-& ...