295. Find Median from Data Stream
題目網址：https://leetcode.cn/problems/find-median-from-data-stream/
題意：中位數是指有序 array 裡中間的數。若 array 長度偶數, 則中位數是中間兩數的平均值。
arr = [2,3,4], 則中位數 = 3
arr = [2,3], 則中位數 = (2+3) / 2 = 2.5
請實現 MedianFinder class：
MedianFinder()：初始化 MedianFinder
void addNum(int num)：新增 num 到資料結構中
double findMedian()：找出目前的中位數
Solution 1：
想法：利用 Balanced BST(紅黑樹), C++ 可直接使用 multiset, 將元素 push 到 multiset 中它會自動排好序。我們用一個 iterator mid 指向目前的中位數（若 multiset 中的元素個數為偶數, 則讓 mid 指向中間靠左的元素）
若 num 加入前, set 中的元素為偶數個(OOXOOO, ...
51. N-Queens
題目網址：https://leetcode.cn/problems/n-queens/
題意：按照國際象棋的規則, 皇后可以攻擊處於同一行 or 同一列 or 同一斜線上的棋子。
n-queens 問題是研究如何將 n 個皇后放在 n x n 的棋盤上, 並使皇后們之間不能互相攻擊。
給一整數 n, 返回所有不同的 n-queens 問題的解法, 可以任意順序返回。
每一種解法包含一種放置棋子的方式, 其中 'Q' 和 '.' 分別代表皇后跟空格。
Solution：
想法：利用 DFS + Backtracking, 單一格之兩條對角線可用公式表示
對角線1：f(x) = x + y, 範圍：[0, 2n - 2] ➔ 總共 2n - 1 條
對角線2：f(x) = x - y, 範圍：[-(n - 1), (n - 1)] ➔ 因為 vector 的 idx 從 0 開始, 所以要將範圍由 [-(n - 1), (n - 1)] 轉為 [0, 2n - 2] ➔ 得新公式：f(x) = x - y + ( ...
332. Reconstruct Itinerary
題目網址：https://leetcode.cn/problems/reconstruct-itinerary/
題意：給一航線列表 tickets, 其中 tickets[i] = [from_i, to_i] 表示飛機出發和降落的地點。請你對該行程進行重新規劃排序。
所有這些機票都屬於一個從 JFK 出發的人, 所以該行程必須從 JFK 開始。如果存在多種有效的行程, 請你按字典排序返回最小的行程組合。
e.g. 行程 ["JFK", "LGA"] 與 ["JFK", "LGB"] 相比就更小, 排序會更靠前
假定所有機票至少存在一種合理的行程。所有的機票都必須使用, 且每張只能用一次
Solution：
首先考慮下面這張圖, 總共有兩條合法路徑：
JFK ➔ AAA ➔ JFK ➔ BBB ➔ JFK
JFK ➔ BBB ➔ JFK ➔ AAA ➔ JFK
由於要選擇字典順序最小的, 所以我們選擇第一條
要如何每次都先拜訪最小的鄰近 node, 並記錄重複的點➔ 將 adj[v] 宣告成 m ...
127. Word Ladder
題目網址：https://leetcode.cn/problems/word-ladder/
題意：一個 transform sequence 指的是 wordList 中從單字 beginWord 到 endWord 的 sequence beginWord -> s1 -> s2 -> ... -> sk, 且 transform sequence 需滿足以下條件：
相鄰的兩個單字只差一個字母
每個 si 都在 wordList 中, 其中 1 ≤ i ≤ k。注意, beginWord 不需在 wordList 中
sk == endWord
給兩個單字 beginWord 和 endWord, 以及一字典 wordList, 返回從 beginWord 到 endWord 的最短 transform sequence 中的單字個數。若不存在這樣的 transform sequence, 則返回 0。
注意：wordList[i] 僅由小寫字母所組成。
Solution 1：
想法：看到最短路徑會直覺想到 Dijkstra, 但在 unweigh ...
778. Swim in Rising Water
題目網址：https://leetcode.cn/problems/swim-in-rising-water/
題意： 在一個 n x n 的整數矩陣 grid 中, 每一個 grid[i][j] 表示位置 (i, j) 的平台高度。
當開始下雨時, 在時間為 t 時, 水池中的水位為 t。你可以從一個平台游向四周相鄰的任意平台, 前提是此時的水位必須同時淹沒這兩個平台才行。假設你可以瞬間移動無限距離, 也就是默認在 grid 內移動是不耗時的。
返回從左上角 (0, 0) 出發, 到達右下角 (n-1, n-1) 所需的最少時間。
Solution：
想法：利用 BFS + Min Heap, 把目前拜訪過的格子之鄰居（未拜訪過的）加入到 min heap pq 中, 然後每次取最小的出來, 直到抵達終點為止, 而 res 就是從 pq 取出過最大的高度
class Solution {public: int swimInWater(vector<vector<int>>& grid) { const ...