Algo 題單 - HackMD

:::info 📢 **README** - 本題單的目的是涵蓋大學演算法課程內容，主要會以 CLRS 作為參考，另佐以各校演算法課程的補充內容。 - 若無特別標註，第一題為和課程內容最為相近的原題，隨後是一些變形題，隱藏的額外題目部分為進階題目，但使用該主題內的知識與技巧便可解出。 - 目前僅 DP 部分較為完整，其餘隨緣更新。 ::: :::warning 📌 除了 LeetCode 的題目外，都可以註冊帳號號在 vjudge 上提交，並可以在 vjudge 上透過搜尋題號和我的帳號 `usaya` 找到我的提交紀錄，但若需要在 vjudge 上提交 Luogu 題目，則需要綁定自己的帳號。 ::: [ToC] --- ## 資料結構 Data Structures ### Basic - [LC 225\. Implement Stack using Queues](https://leetcode.com/problems/implement-stack-using-queues/) - [LC 232\. Implement Queue using Stacks](https://leetcode.com/problems/implement-queue-using-stacks/) ### Queue :::spoiler 額外題目 - [ABC389C - Snake Queue](https://vjudge.net/problem/AtCoder-abc389_c) ::: ### Deque ### Heap - [LC 703\. Kth Largest Element in a Stream](https://leetcode.com/problems/kth-largest-element-in-a-stream/) `[112台大]` 經典題。 - [LC 295\. Find Median from Data Stream](https://leetcode.com/problems/find-median-from-data-stream/) `[112台大]` 經典題。注意是 Data Stream。 :::spoiler 額外題目 - [ABC376E - Max × Sum](https://atcoder.jp/contests/abc376/tasks/abc376_e) :::spoiler 💡Hint 排序後，枚舉右端點的 A ，並維護左端點最小的 K 個 B 的和 ::: ::: ### Ch19. Disjoint Sets - [LC 684. Redundant Connection](https://leetcode.com/problems/redundant-connection/) - [UVA-793 Network Connections](https://vjudge.net/problem/UVA-793) :::spoiler 額外題目 - [1631. Path With Minimum Effort](https://leetcode.com/problems/path-with-minimum-effort/) `[107 台大]` 本題也有最短路、二分答案求最大化最小值做法。 :::spoiler 💡Hint 將每條邊排序後，將 w 從小到大排序後，依次將每條邊的兩個端點 u, v 連通，直到起點和終點在一個連通分量中結束。 ::: - [ABC380E - 1D Bucket Tool](https://vjudge.net/problem/AtCoder-abc380_e) :::spoiler 💡Hint - 在一般的 Disjoint Set 外額外維護每個 conneted component 的顏色以及每個顏色的數量，供操作 2 使用。 - 但合併時改成依照每個 component 的左端點合併，即 $x$ 所屬區間的左端點為 $f_x = find(x)$，由於 component 是連續的區間，可以得右端點為 $f_x + sz[fx] - 1$。 - 故更改顏色後檢查 $f_x - 1$ 和 $f_x + sz[f_x]$ 是否需要和 $f_x$ 合併即可。由於先合併 $f_x - 1$ 可能會導致 $f_x$ 改變，因此需要重新取一次 $f_x$ 或先合併右再合併左。 📗 [解題紀錄](https://gdst.dev/posts/ATC_ABC380/#%F0%9F%94%97-E-1D-Bucket-Tool-abc380-E) ::: ::: ### Trie > NCKU DS :::danger 📌 今年成大資料結構更換授課老師，出題老師是否更換尚且未知，請自行衡量是否需要準備舊老師的授課內容。 ::: - [LC 208\. Implement Trie (Prefix Tree)](https://leetcode.com/problems/implement-trie-prefix-tree/) :::spoiler 額外題目 - [Luogu P1481 魔族密码](https://www.luogu.com.cn/problem/P1481) :::spoiler 💡Hint 維護字典樹上該條路徑上出現的單字數量即可。 ::: - [ABC377G - Edit to Match](https://vjudge.net/problem/AtCoder-abc377_g) :::spoiler 💡Hint 在 Trie 中維護每個節點往下走到最近的單字結尾的距離，則在查詢時，對於 $S_k$ 的每個位置 $i$，只需要將目前位置需要的刪除數量 $n - 1 - i$ 與前述維護的距離相加即可。 ::: ::: ## 分治法 Divide and Conquer ### Tower of Hanoi > NTU ADA - [CSES-2165 Tower of Hanoi](https://vjudge.net/problem/CSES-2165) - [Luogu P1096 Hanoi 双塔问题](https://www.luogu.com.cn/problem/P1096) 圓盤的數量為 $2n$，但這題的難點其實在高精度上，只想推公式的話直接用 Python 提交就好 - [UVA-10254 The Priest Mathematician](https://vjudge.net/problem/UVA-10254) 增加一個中間柱，可以寫出遞迴式後觀察規律，同樣有高精度的要求，只想推公式的話同樣可以使用 Python 提交就好 ### Closest Pair Problem > NTU ADA, NYCU Algorithm - [UVA-10245 The Closest Pair Problem](https://vjudge.net/problem/UVA-10245) ### Maximum Subarray Sum > NTU ADA, NCKU Algorithm - [LC 53. Maximum Subarray](https://leetcode.com/problems/maximum-subarray/) `[113 中興]` `[107 中央]` - 教科書和課程中介紹的都是 combine 需要 $O(n)$ 的解法，總時間複雜度為 $O(n \log n)$，但其實透過維護其他性質，combine 可以做到 $O(1)$，總時間複雜度為 $O(n)$。 - 另外本題也有前綴和和動態規劃解法。📗 [解題紀錄](https://gdst.dev/posts/LC-53/) ## 貪心/貪婪 Greedy ### Activity Selection Problem > NTU ADA, NYCU Algo - [LC 646. Maximum Length of Pair Chain](https://leetcode.com/problems/maximum-length-of-pair-chain/) - [LC 435. Non-overlapping Intervals](https://leetcode.com/problems/non-overlapping-intervals/) - [LC 452. Minimum Number of Arrows to Burst Balloons](https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/) ### Breakpoint Selection Problem :::warning 🧩 暫時找不到比較貼近的題目，這裡放的是也是加油的另一種貪心問題。(反悔貪心) ::: - [LC 871\. Minimum Number of Refueling Stops](https://leetcode.com/problems/minimum-number-of-refueling-stops/) :::spoiler 額外題目 - [Luogu P2949 [USACO09OPEN] Work Scheduling G](https://www.luogu.com.cn/problem/P2949) :::spoiler 💡Hint 按照 deadline 分組，並按照時間做所有任務，遇到目前做了太多任務時，則反悔，選擇前面收益最小的放棄。 ::: - [AIsing2020E - Camel Train](https://atcoder.jp/contests/aising2020/tasks/aising2020_e) :::spoiler 💡Hint 類似 Luogu P2949，但需要根據擺在左邊還是右邊哪邊的收益比較高先進行一次分組，再對兩組分別做反悔貪心，注意方向已經允許的大小。 ::: ::: ## 動態規劃 Dynamic Programming (DP) ### 14.1 Rod cutting (線性DP) - [Gym-270304F Rod Cutting](https://vjudge.net/problem/Gym-270304F) ### Maximum Subarray Sum (Kadane's Algorithm) - [LC 53\. Maximum Subarray](https://leetcode.com/problems/maximum-subarray/) `[113 中興]` `[107 中央]` - 可以考慮空間優化，另有前綴和以及 $O(n)$ 的分治作法。📗 [解題紀錄](https://gdst.dev/posts/LC-53/) - [LC 152\. Maximum Product Subarray](https://leetcode.com/problems/maximum-product-subarray/) LC 53 延伸，可以考慮多維護一個值。 - [LC 1749\. Maximum Absolute Sum of Any Subarray](https://leetcode.com/problems/maximum-absolute-sum-of-any-subarray/) - [LC 2606\. Find the Substring With Maximum Cost](https://leetcode.com/problems/find-the-substring-with-maximum-cost/) :::spoiler 額外題目 - [LC 2272. Substring With Largest Variance](https://leetcode.com/problems/substring-with-largest-variance/) :::spoiler 💡Hint - 若已知在答案中出現次數最多和最少的字母分別為 $a$ 和 $b$，則可以將 $a$ 視為 $1$，$b$ 視為 $-1$，其他字母視為 $0$，如此題目所求即為對其求 Maximum Subarray Sum。 - 由於 $b$ 一定要出現，因此需要額外維護一個狀態紀錄 $b$ 是否出現過。 - 雖然 $(a, b)$ 是未知的，但所有可能只有 $P^{26}_2 = 650$ 種，可以枚舉所有可能。 - 若枚舉的 $a^{\prime}$ 並不是真正的 $a$，或若枚舉的 $b^{\prime}$ 並不是真正的 $b$，則最大子陣列和都會變小，不會影響答案。 ::: ::: ### 14.2 Matrix-Chain Multiplication (區間DP) - [Aizu-ALDS1_10_B Matrix Chain Multiplication](https://vjudge.net/problem/Aizu-ALDS1_10_B) - [UVA-348 Optimal Array Multiplication Sequence](https://vjudge.net/problem/UVA-348) 需要構建結果 - [LC 312. Burst Balloons](https://leetcode.com/problems/burst-balloons/) 變形，但不要被 Hard 嚇到了，只需要做一些處理即可，可以想想這題為甚麼會被分到這裡 XD ### Optimal Polygon Triangulation (區間DP) > NYCU Algorithm :::success 📝 三角形的價值可以是邊的權重和、點的權重和、面積。 ::: :::warning 💡 除了最大或最小化三角分割多邊形價值外，那要如何求凸多邊形的分割方法數呢？提示：離散與組合數學。 :::spoiler 答案 ==**卡塔蘭數 (Catalan number)**== - 🔗 [卡特兰数 - OI Wiki](https://oi-wiki.org/math/combinatorics/catalan/) - 🎞️ [算法讲解147【扩展】卡特兰数题型详解和取模处理](https://www.bilibili.com/video/BV1BACUY7EzN/) ::: - [LC 1039. Minimum Score Triangulation of Polygon](https://leetcode.com/problems/minimum-score-triangulation-of-polygon/) - [CF 1140D. Minimum Triangulation](https://vjudge.net/problem/CodeForces-1140D) 因為 $n = 500$，所以可以用 $O(n^3)$ 的DP解法，此外也有 $O(n)$ 的貪心解法 :::spoiler 額外題目 - [UVA-1331 Minimax Triangulation](https://vjudge.net/problem/UVA-1331) 注意和上面的題目不同，此題沒有保證是凸邊形，故轉移時需要判斷是否合法，且定義的價值是面積，可以使用海龍公式。 ::: ### 14.4 Longest Common Subsequence (區間DP) - [UVA-10405 Longest Common Subsequence](https://vjudge.net/problem/UVA-10405) - [LC 583\. Delete Operation for Two Strings](https://leetcode.com/problems/delete-operation-for-two-strings/) 變形，但不多 - [LC 712\. Minimum ASCII Delete Sum for Two Strings](https://leetcode.com/problems/minimum-ascii-delete-sum-for-two-strings/) 變形 ### 14.5 Optimal binary search trees (區間DP) - [Aizu-ALDS1_10_D Optimal Binary Search Tree](https://vjudge.net/problem/Aizu-ALDS1_10_D) - [Luogu P2308 添加括号](https://www.luogu.com.cn/problem/P2308) `108 交大` 變形，注意是合併只能發生在相鄰兩項間，因此不能貪心。且需要重建結果。此外定義和 OBST 略有不同，邊界條件為 $f(i, i) = 0$，且轉移的 cost 為 $\displaystyle \sum_{k=i}^{j} nums[k]$。 - [Luogu P1880 [NOI1995] 石子合并](https://www.luogu.com.cn/problem/P1880) 變形，和 P2308 類似，但本題要同時求最大和最小值。 ### P14-2 Longest Palindrome Subsequence (區間DP) - [LC 516. Longest Palindromic Subsequence](https://leetcode.com/problems/longest-palindromic-subsequence/) - [UVA-11151 Longest Palindrome](https://vjudge.net/problem/UVA-11151) 測資中有空行，且需要對空行計算 LPS 長度 ### P14.4-5&6 Longest Increasing Subsequence - [LC 300\. Longest Increasing Subsequence](https://leetcode.com/problems/longest-increasing-subsequence/) 求長度 - [1671\. Minimum Number of Removals to Make Mountain Array](https://leetcode.com/problems/minimum-number-of-removals-to-make-mountain-array/) `113交大` - 前後綴分解，類似113交大手寫，只有求答案的部分不同。📗 [解題紀錄](https://gdst.dev/posts/LC-1671/) #### 二維 LIS - [UVA-437 The Tower of Babylon](https://vjudge.net/problem/UVA-437) - [LC 354\. Russian Doll Envelopes](https://leetcode.com/problems/russian-doll-envelopes/) 這題現在 $O(n^2)$ 的 DP 會 TLE ，一定要 $O(n \log n)$ 的貪心才能AC，但還是可以參考原本的 [官方題解](https://leetcode.cn/problems/russian-doll-envelopes/solutions/633231/e-luo-si-tao-wa-xin-feng-wen-ti-by-leetc-wj68) :::spoiler 額外題目 - [Luogu P1233 木棍加工](https://www.luogu.com.cn/problem/P1233) 這題的結論上是一維非遞增(>=)、另一維遞增(<)。在推出結論的過程會用到 Dilworth's theorem ，其通俗解釋是把一個序列劃分成 **最少** 個非遞增子序列的數目，等於這個序列的最長遞增子序列的長度(LIS)，怎麼推出這個結論的對考研來說不是很重要。 ::: ### P14-4 Edit Distance (區間DP) - [CSES-1639 Edit Distance](https://vjudge.net/problem/CSES-1639) ### P15-1 Coin changing (背包DP) - [CSES-1634 Minimizing Coins](https://vjudge.net/problem/CSES-1634) 問最少硬幣數量，同 [LC 322\. Coin Change](https://leetcode.com/problems/coin-change/) - [CSES-1635 Coin Combinations I](https://vjudge.net/problem/CSES-1635) 問排列數 - [CSES-1636 Coin Combinations II](https://vjudge.net/problem/CSES-1636) 問組合數，同 [LC 518\. Coin Change II](https://leetcode.com/problems/coin-change-ii/) - [UVA-11407 Squares](https://vjudge.net/problem/UVA-11407) 變形，同 [LC 279\. Perfect Squares](https://leetcode.com/problems/perfect-squares/) - [CSES-1633 Dice Combinations](https://vjudge.net/problem/CSES-1633) 變形，分組背包 - [LC 1155\. Number of Dice Rolls With Target Sum](https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/) 變形，分組背包，骰子點數增加 ### Weighted Interval Scheduling / Weighted Job Scheduling (劃分DP) > NTU ADA :::success 💡 可以關注如何要找到第一個兼容的區間 ::: - [LC 2830\. Maximize the Profit as the Salesman](https://leetcode.cn/problems/maximize-the-profit-as-the-salesman/) - [LC 2008\. Maximum Earnings From Taxi](https://leetcode.com/problems/maximum-earnings-from-taxi/) ## 二分搜尋 Binary Search ### 最小化最大值 ### 最大化最小值 - [1631. Path With Minimum Effort](https://leetcode.com/problems/path-with-minimum-effort/) `[107 台大]` 本題有最短路、二分答案求最大化最小值、Disjoint Set 做法。 ## 圖論演算法 Graph Algorithms :::info 🔗 [【题单】图论算法（DFS/BFS/拓扑排序/最短路/最小生成树/二分图/基环树/欧拉路径） ](https://leetcode.cn/circle/discuss/01LUak/) ::: ### DFS :::spoiler 額外題目 - [ABC378F - Add One Edge 2](https://vjudge.net/problem/AtCoder-abc378_f) :::spoiler 💡Hint 對於一個==度數皆為 $3$ 的連通分量==，可以計算他相鄰的點中度數為 $2$ 的點的數量 $cnt$，在這些度數為 $2$ 的點中，任選兩個配對，即可滿足題目要求，故這個連通分量對答案的貢獻為 $\frac{cnt \times (cnt - 1)}{2}$，也可以用 BFS 求解。 ::: ::: ### BFS - [UVA-532 Dungeon Master](https://vjudge.net/problem/UVA-532) 三維空間 ### 20.4 Topological sort - [LC 1462. Course Schedule IV](https://leetcode.com/problems/course-schedule-iv/) 計算 `ans[u][v]` 時可以在拓樸排序過程中找前面的節點，或是拓樸排序結束後用 Floyd-Warshall 求解。 ### Ch21. Minimum Spanning Tree - [LC 1584\. Min Cost to Connect All Points](https://leetcode.com/problems/min-cost-to-connect-all-points/) - [Luogu P1547 [USACO05MAR] Out of Hay S](https://www.luogu.com.cn/problem/P1547) ### Ch22. Single-Source Shortest Paths - [CSES-1671 Shortest Routes I](https://vjudge.net/problem/CSES-1671) - [LC 743\. Network Delay Time](https://leetcode.com/problems/network-delay-time/) - [1631. Path With Minimum Effort](https://leetcode.com/problems/path-with-minimum-effort/) `[107 台大]` 本題也有二分答案求最大化最小值、Disjoint Set 做法。 - [1368\. Minimum Cost to Make at Least One Valid Path in a Grid](https://leetcode.com/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid/) - [UVA-10000 Longest Paths](https://vjudge.net/problem/UVA-10000) 變形，注意給定的是 DAG - [LC 3341\. Find Minimum Time to Reach Last Room I](https://leetcode.com/problems/find-minimum-time-to-reach-last-room-i/) 變形 ### Ch23. All-Pairs Shortest Paths - [CSES 1672_Shortest Routes II](https://vjudge.net/problem/CSES-1672) - [LC 2976\. Minimum Cost to Convert String I](https://leetcode.com/problems/minimum-cost-to-convert-string-i/) - 📗 [解題紀錄](https://gdst.dev/posts/LC-2976/) - [LC 1462. Course Schedule IV](https://leetcode.com/problems/course-schedule-iv/) 需要拓樸排序。 ### Ch24. Maximum Flow :::success 💡可以參考 OI-WIKI 和 AtCoder Library 中的實現。不過網路流的問題難點其實在如何建圖，但對考研來說應該不用研究如何針對問題建圖。 ::: - [Luogu P3376 【模板】网络最大流](https://www.luogu.com.cn/problem/P3376) ## Misc ### Maximum Gap > NYCU Algorithm - [LC 164. Maximum Gap](https://leetcode.com/problems/maximum-gap/) 做到 $O(n)$ ### Next Combination / Permutation - [LC 31. Next Permutation](https://leetcode.com/problems/next-permutation/) > 某校某年的數學題目，知道出處的歡迎留言告知 - 做到 $O(n)$。📗 [解題紀錄](https://gdst.dev/posts/LC-31/) - [LC 1286. Iterator for Combination](https://leetcode.com/problems/iterator-for-combination/description/) `106中央` - [NC286220 同位序列](https://ac.nowcoder.com/acm/problem/286220) - 有做過前面 DP 題目的話本題 DP 部分很簡單，主要思考 $g(x)$ 的求法即可。 :::spoiler 💡Hint - 由於 $x$ 和 $g(x)$ 二進位表示中 $1$ 的個數相同，因此可以使用一個陣列儲存 $x$ 的二進位表示，在前面補 $0$ 後對其求下一個排列即可。時間複雜度 $O(\log x)$。 - 另有 $O(1)$ 的位運算做法。 :::