# 分析解題思路

1. 維持極值以便修改資料池：heap, monotonics
2. 數字：注意overflow，注意題目範圍
3. 高速存取：map, hash; 且常變動：deque, LL, DLL + array
4. 有序找第一個：二分搜尋、單調性結構
5. 二元樹：可DP、DFS
6. 排列分組問題：DFS -> prune -> DP
7. 排序用在一開始才可靠，否則超時
8. 加速迴圈靠剪枝、排序
9. 樹圖最小總成本：MST
10. 圖最小成本的路徑：Dijkstra (heap-based BFS)
11. 小範圍：DP -> DFS

* lc-4: Median of Two Sorted Arrays
* 搜尋大陣列，用簡單做法會太慢
* 二分搜尋
* lc-7 Reverse Integer
* 十進位制操作，注意overflow
* 先比位數，再由大位比到小位，2147483647
* lc-146 LRU Cache
* map結構，存取要夠快
* LRU，注重順序用queue結構
* LRU，變更順序用DLL O(1)取代deque O(n)
* lc-218 The Skyline Problem
* 注意題目特殊情況
* 只需維持目前最高狀態用heap O(1)
* lc-739 Daily Temperatures
* 往右邊數第一個比自己大
* 單調性結構 O(n) 不要 O(n^2)
* zoj BST preorder
* 先操作，再傳到左邊，最後傳到右邊
* zoj 加分二元樹
* 定位子問題，需DP
* uva-109 SCUD Busters
* 二維極坐標掃描線問題
* 題目提示一定有用：外積
* 先取左下參考點，用外積正負號排序 O(nlogn)
* lc-792 Number of Matching Subsequences
* 字母表，紀錄字元位置：[character : [index]]
* 由左到右第一個最大的數字，用二分搜尋 upper_bound(first, last, value)
* lc-76 Minimum Window Substring
* 最短string作為superset，雙指標問題：min window
* 指標重合就更新數據
* lc-473 Matchsticks to Square
* 有排列組合的感覺，試錯的部分可以看作DFS分支
* DFS剪枝要設條件，或是DP
* lc-684 Redundant Connection
* 樹圖多一個連結怎麼去掉？
* Disjoint Set判斷Cycle，一直union到了同parent表示將出現Cycle
* lc-18 4Sum
* 全部迴圈不可能夠快，得剪枝（陣列先排序）
* 2Sum + 2層迴圈，2Sum往中靠
* uva-104 Arbitrage
* 走最短的路才滿足條件，不是BFS
* 小範圍，大概是DP
* 子問題：答案是否滿足1.05的條件，否則合併其他子問題的答案
* lc-95 Unique Binary Search Trees II
* 排列組合，小範圍，DFS或DP
* 子問題：誰是根點？誰在左支？誰在右支？傳給下一個根點
* poj-3253 Fence Repairing
* 一分為二，像是樹，由成本定義：切到的總長度，切到視為利用
* 最短利用最多次，最長利用最少次，Huffman (use heap pop 2 into 1 and push in)
* lc-1584 Min Cost to Connect All Points
* 是樹圖，最小總成本，MST (sort then use disjoint set to avoid cycle)
* lc-743 Network Delay Time
* 最小成本路徑，Dijkstra (use priority queue + BFS)
* lc-6 Zigzag Conversion
* 觀察並推導
* lc-307 Range Sum Query - Mutable
* segment tree (use 2n array as tree)
* lc-295 Find Median from Data Stream
* 找動態陣列中的中位數，用排序會超時 O(nlogn)，就用heap維護 O(logn)
* uva-222 Budget Travel
* 變數一大堆，用特徵取名字，例如單位
* 小範圍，是DFS還是DP？
* 找最小成本，可能會找到太大的路線，回頭再找，用DFS每次回傳時更新答案到最小
* lc-239 Sliding Window Maximum
* 取得一個動態範圍每次的最大值，雙指標問題 min window
* 每次更新最大值用簡單方法 O(n) 應該會太久，用heap？如果超出範圍要刪除
* 用單調性結構，monotonic queue
* lc-1278 Palindrome Partitioning III
* 不需要確認回文性，因為要算變化次數（成本）
* 排列組合，小範圍，大概DP
* Longest CS
* `if c1 == c2: dp[i1][i2] = dp[i1 - 1][i2 - 1] + 1`
* `else: dp[i1][i2] = max(dp[i1 - 1][i2], dp[i1][i2 - 1])`