---
# System prepended metadata

title: 分析解題思路

---

# 分析解題思路

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])`