678. Valid Parenthesis String
題目網址：https://leetcode.cn/problems/valid-parenthesis-string/
題意：給一只包含三種 char （ 、） 和 * 的 string s, 判斷 s 是否為有效的 string。有效的 string 具有如下規則：
任何左括號 ( 必須有相應的右括號 )
任何右括號 ) 必須有相應的左括號 (
左括號 ( 必須在對應的右括號之前 )
* 可以被視為單個右括號 ) or 單個左括號 ( or 一個 empty string ""
empty string "" 也被視為有效的 string。
Solution：
想法：利用 Greedy, 由於 * 有三種可能, 因此我們需要用 leftMin、leftMax 來記錄未匹配左括號的範圍
leftMax 代表未匹配左括號的最大數量, 也就是將所有 * 都變成 (
leftMin 代表未匹配左括號的最小數量, 也就是將所有 * 都變成 )
一旦 leftMax < 0, 代表 s 中 ) 太多, 將所有 * 都變成 ( 也無法匹配 ...
57. Insert Interval
題目網址：https://leetcode.cn/problems/insert-interval/
題意：給一無重疊的 interval array intervals, 且 intervals 已根據 intervals[i][0] 做升序排列。
今插入一區間 newInterval, 必須確保插入後 intervals 仍升序排列且不重疊 (如果有必要的話, 可以合併區間)
Solution：
想法：先將 newInterval 插入 intervals 中的正確位置, 然後再利用 56. Merge Intervals 進行 merge
class Solution {public: vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) { auto it = intervals.begin(); // 根據 start 將 n ...
56. Merge Intervals
題目網址：https://leetcode.cn/problems/merge-intervals/
題意：給一 array intervals, 其中 intervals[i] = [start_i, end_i], 合併所有重疊的區間, 並返回一個不重疊區間 array。
Solution：
想法：類似 252. Meeting Rooms, 先根據 intervals[i].start 做排序, 若 interval[i].start ≤ res.back().end 的話代表有重疊, 則將當前的 interval.end 設為兩者 end 中較大的（合併）; 若無重疊, 則將 interval[i] 加入到 res 中
class Solution {public: vector<vector<int>> merge(vector<vector<int>>& intervals) { sort(intervals.begin(), intervals.end()); ...
1584. Min Cost to Connect All Points
題目網址：https://leetcode.cn/problems/min-cost-to-connect-all-points/
題意：給一整數 array points, 表示 2D 平面上的一些點, 其中 points[i] = [x_i, y_i] 。
連接點 [x_i, y_i] 和點 [x_j, y_j] 的費用為它們之間的曼哈頓距離：
|x_i - x_j| + |y_i - y_j|
其中 |val| 表示 val 的絕對值。
返回將所有點連接的最小總費用。
Solution 1：
想法：本題其實就是在求 MST (Minimum Spaning Tree), 故利用 Kruskal 演算法, 每次選擇 cost 最小的邊 e, 若加入 e 會導致 graph 中有 cycle（用 Union Find 判斷）, 則跳過 e, 直到 graph 中有 n - 1 條邊
typedef tuple<int, int, int> t3i;class Solution {public: int minCostConnectPoint ...
743. Network Delay Time
題目網址：https://leetcode.cn/problems/network-delay-time/
題意：有 n 個網路節點, 標記為 1 到 n。
給一 list times, 表示訊號經過有向邊的傳遞時間。times[i] = (ui, vi, wi), 其中 ui 是起點、vi 是終點, 而 wi 是一個訊號從起點傳遞到終點的時間。
從某個節點 k 發出一個訊號, 返回需要多久才能使所有節點都收到訊號？如果不能使所有節點都收到訊號, 則返回 -1 。
Solution：
想法：利用 Dijkstra 演算法（BFS + Heap）, 而非單純 BFS, 因為 weight 有可能不為 1, 這樣會導致 BFS 所得出之答案未必為解答。步驟如下：
建立 adjacent lit
建立 min heap
執行 BFS
➔ BFS 中得到未拜訪過的點 cur , 則 dis 必為起點 k 到 cur 的最短路徑
e.g. 下圖中, 求 1 到 2 的時間
若用 BFS 求解, 則 path 為 1 ➔ 2, 得出 4
正確的 path 應為 1 ➔ 3 ➔ 4 ➔ ...