261. Graph Valid Tree
題目網址：https://leetcode.cn/problems/graph-valid-tree/
題意：給定編號 0 到 n - 1 的 n 個 node, 和一個無向邊的 list edges, 其中 edges[i] = [a, b] 代表 graph 中 a 和 b 之間有一邊, 返回此 graph 是否為 tree。
注意：edges 中沒有重複的邊（e.g. [1, 0] 和 [0, 1] 不會同時出現在 edges 中）
Solution 1：
想法：利用 DFS, 若 graph 要為 tree, 則必須滿足以下兩點：
graph 中不可有 cycle
graph 必須為 connected, 也就是圖中任兩點必定有邊相連, 不能有 isolated vertex
class Solution {public: bool validTree(int n, vector<vector<int>> &edges) { vector<vector<int>> ad ...
33. Search in Rotated Sorted Array
題目網址: https://leetcode.cn/problems/search-in-rotated-sorted-array/
題意: 有一整數 array nums 按升序排列, 其中的值互不相同。
給一旋轉後的 array nums 和一整數 target, 如果 nums 中存在 target, 則返回其 index; 否則, 返回 -1。
請設計 $O(log(n))$ time 的演算法。
Solution：
想法：利用 Binary Search, 將 nums 從中間分開成左右兩部分的時候, 一定有一部分是有序的。
e.g. nums = [4,5,6,7,0,1,2], 從 6 切割, 可分成 [4,5,6] 和 [7,0,1,2] 兩個部分, 其中左邊 [4,5,6] 是有序的
因此我們可以在 Binary Search 時查看當前 mid 分割的兩個部分 [left, mid] 和 [mid + 1, right] 中哪個是有序的, 藉此來縮小左邊界 or 右邊界。
若 target == nums[mid], 則直接返回 mid
若 [left, m ...
981. Time Based Key-Value Store
題目網址：https://leetcode.cn/problems/time-based-key-value-store/
題意：設計一個基於時間的 key-value 的資料結構, 它可以在不同 timestamp 儲存對應同一個 key 的多個值, 並針對特定 timestamp 得到相對應的 key 的 value。
實作 TimeMap class：
TimeMap() : 初始化 instance
void set(String key, String value, int timestamp) : 儲存 key、 value, 以及 timestamp。
String get(String key, int timestamp) :
返回 timestamp_prev 對應的 value, 其中 timestamp_prev <= timestamp
如果存在多個值, 則返回對應最大的 timestamp_prev 的 value。
如果不存在, 則返回 ""。
注意: set(key, value, timestamp) 中的 time ...
143. Reorder List
題目網址：https://leetcode.cn/problems/reorder-list/
題意：給一單向 linked list 的起始節點 head, 該 linked list 可表示為
L0 → L1 → … → Ln - 1 → Ln
將其重新排序為
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
不能只是單純改變節點內部的值, 必須進行實際的節點交換。
Solution：
想法：分成以下步驟
找到 linked list 的中點, 按照 141. Linked List Cycle 的方法
奇數時, mid 指向中點
偶數時, mid 指向右中點
因此, 最一開始要先讓 fast 先走一步, 這樣不管是奇偶數, mid 都會指向左中點
重要：截斷兩個 list ➔ mid->next = nullptr（容易忘記這步）
reverse 右半部分 Ln → Ln - 1 → Ln - 2 → ...
merge 左半和右半
class Solution {public: void reorderLis ...
19. Remove Nth Node From End of List
題目網址：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
題意：給一 linked list, 請刪除倒數第 n 個 node, 並返回 linked list 的 head。
進階：試著用一次掃描就完成。
Solution：
想法：利用 slow & fast pointers, 用 dummy 是因為有可能第一個 node 被刪, 所以需要有 ptr 指著第一個 node 的前一個 node。首先 fast 先從 head 走 n 步（讓 fast 領先）, 然後 slow 才從 dummy 開始往前走, 直到 fast 變成 NULL
為什麼 fast 是初始化為 head, 而 slow 初始化為 dummy ?因為若 fast 和 slow 都初始化為 head, 則當 fast 為 NULL 時, slow 恰好在倒數第 n 個 node(因為 fast 領先 n 步), 但是我們是要刪除倒數第 n 個 node, 要取得的是倒數第 n 個 node 的前一個節點(倒數第 n + ...