LeetCode（力扣）主站難題Top30盤點（2023-6） 天天觀察

LeetCode（力扣）是一個面試向刷題平臺，大多數題目的難度遠遠不及CodeForces，atcoder等競賽OJ。在題目風格上，力扣平臺更重視考察用戶對知識點的熟悉程度，而競賽OJ則主要考察思維，因此競賽OJ大多數題目不適合面試，而力扣平臺也不能用于OI/ACM選手。

(相關資料圖)

但與此同時，力扣平臺還是存在一些題目有一定難度，這些題目出現在筆試里，往往不是必須通過全部case才能進面，而如果出現在面試里，基本就是告訴應聘者已經招滿了。本專欄盤點截止2023年前半年，UP個人認為的主站題目（不包括LCP和劍指專輯，面試金典專輯）難度前30名。注意本專欄只考慮思維難度，知識點超綱但學過對應知識點就90%以上概率會做的題目一律不入選。

Top30????1595 連接兩組點的最小成本

https://leetcode.cn/problems/minimum-cost-to-connect-two-groups-of-points/

這道題首先要做一個思維轉換，題意是要求cost矩陣中選取一些元素，且每行每列都必須有元素入選，求所選元素最小值。看起來是一道很裸的狀態壓縮DP，但每行并不一定只選1個元素最優，為了能在合理的時間復雜度內考慮到每行選多列的情況，就需要在同一行內狀態轉移。

Top29????1494 并行課程II

https://leetcode.cn/problems/parallel-courses-ii/

這道題目的零神大數據難度分不高，是因為比賽期間絕大多數通過的代碼都是錯誤的貪心。本題用拓撲排序是不通的，正解應該是狀態壓縮DP。對于每一種狀態，都需要枚舉接下來可以學的課程的所有不超過k門的組合，如果實現有漏洞，很容易TLE。

Top28? ? 2281 巫師的總力量和

https://leetcode.cn/problems/sum-of-total-strength-of-wizards/

這道題本質上是貢獻法，需要單調棧來確定每個元素的作用區間，但多個子數組的最小值與數組和的乘積的和不是一個簡單的區間和問題。要解決這個問題，或者引入前綴和的前綴和，或者用所有a[i]-i構成新數組的前綴和，而這都是力扣平臺幾乎涉及不到的。

Top27????480 滑動窗口中位數

https://leetcode.cn/problems/sliding-window-median/

這道題看似是239和295的拼接，但實際上不但需要大頂堆和小頂堆各1個，還用到了延遲刪除的技巧，為了保證兩個堆數據量的平衡，實現細節相當多。當然本題如果用Python語言的SortedList，那就是Easy題了。

Top26????420 強密碼檢驗器

https://leetcode.cn/problems/strong-password-checker/

這道題看似只是實現細節很繁瑣，但實際上輸出長度超過20是極難處理的，因為不能保證只刪除超出限制的數量的字母就能讓其成為強密碼。替換操作和刪除操作如何選擇需要以連續相同字母數對3取模為依據，做較復雜的分類討論。

Top25????2071 你可以安排的最多任務數目

https://leetcode.cn/problems/maximum-number-of-tasks-you-can-assign/

這道題的正解確實是貪心，但不能直接貪，否則磕藥的時機無法確定。正確做法是二分猜答案，驗證答案可否為k時直接看最強的k的工人和最簡單的k個任務。

Top24????2127 參加會議的最多員工數

https://leetcode.cn/problems/maximum-employees-to-be-invited-to-a-meeting/

這道題的零神大數據難度分不是特別離譜，是因為力扣平臺比賽期間可以看WA的case。找最大的環確實沒錯，但答案還有另一種可能，就是一對戀人坐在一條長鏈上。

Top23????2499 讓數組不相等的最小總代價

https://leetcode.cn/problems/minimum-total-cost-to-make-arrays-unequal/solution/li-yong-nums10-tan-xin-zhao-bu-deng-yu-z-amvw/

這道題有“工具人”思想，主要坑點有兩個，一是需要交換的數量是奇數并不一定無解，可以利用無代價的nums[0]做媒介，二是如果需要交換的部分的眾數頻率超過50%時不能直接返回答案，必須讓已經滿足條件的部分做出犧牲。

Top22????2573 找到對應LCP矩陣的字符串

https://leetcode.cn/problems/minimum-total-cost-to-make-arrays-unequal/solution/li-yong-nums10-tan-xin-zhao-bu-deng-yu-z-amvw/

這道題構造本身就有相當的思維難度，而構造之后必須用DP的方法去完整驗證更是大多數人難以直接想到的，之所以需要驗證是因為構造的過程沒有利用LCP的所有性質。大部分比賽代碼都被rejudge沒了，即使放到CF里如果必須驗證的數據都在system test里，難度分也不太會低于2000。

Top21????2386 找出數組的第K大和

https://leetcode.cn/problems/find-the-k-sum-of-an-array

這道題最反直覺的是需要把所有負數都變成正數，這是合理的，因為假設數組所有非負數的和為sum，任意子序列的和都是sum拿掉一些正數再加上一些負數。sum就是最大的一個，接下來就是在sum的基礎上，從小到大枚舉已經沒有負數的所有子序列和，具體的枚舉方法需要借助堆，并且為了避免出現重復，子序列和需要帶下標信息。出堆1個子序列時至多入隊2個新的子序列（下一個下標要或不要），因此以本題k的范圍，堆里只有很少的子序列，不會TLE。

Top20????1330 翻轉子數組得到最大的數組值

https://leetcode.cn/problems/reverse-subarray-to-maximize-array-value/

這道題為了在合理的時間復雜度內通過，必須用移項的技巧，而且想要避免過于繁雜的分類討論，就要用數學表達式來歸納各種情況，不用草稿紙靠心算幾乎是不可能的。周賽里這道題是10分題雖然顯得夸張，但確實在LC上有相當的難度。

Top19????803 打磚塊

https://leetcode.cn/problems/bricks-falling-when-hit/

這道題看似只是在305的基礎上加了個逆序思維，但是否連通不能只看矩陣本身，還要考慮邊界，所以并查集的大小不能是m*n，這和LCP71有點類似。由于每次操作不能遍歷整個parents，并查集內需要維護每個位置的鄰居數量。

Top18? ? 546 移除盒子

https://leetcode.cn/problems/remove-boxes/

這道題目雖然明顯是DP，但很容易給出錯誤的狀態定義和轉移。由于每次消除都有可能把本來不相鄰的位置變得相鄰，因此為了考慮這種情況，狀態定義要加上一個維度，這個維度是當前區間的后面還有多少個和當前右端點顏色相同的盒子。

Top17????818 賽車

https://leetcode.cn/problems/race-car/

這道題看起來有點抽象，需要舉一些較小的例子來找規律。首先要找出能成為最優序列必須要有的特征，這樣才能確定如何進行狀態轉移，然后要注意超過終點時應當立即掉頭，超過target的位置的狀態不需要專門計算。

Top16????964 表示數字的最少運算符

https://leetcode.cn/problems/least-operators-to-express-number/

這道題的target范圍很大，肯定不能對每個狀態都考慮添加各種運算符，正確的思路是用乘法快速接近target或超過target，然后超出的部分一直遞歸下去，直到超出的部分為0，但要注意乘號數量一定要考慮“最接近”和“超過”兩種情況。具體實現細節很多。

Top15????1896 反轉表達式值的最少操作次數

https://leetcode.cn/problems/minimum-cost-to-change-the-final-value-of-expression/

表達式解析本身就不是很簡單，而更改操作更容易讓人毫無頭緒。不過注意到表達式值只有2種，所以DP的狀態定義應當就是讓某個區間的表達式值為0或1所需要的操作數。枚舉所有區間肯定會TLE，因此應當用主站224題的方法，按順序邊用棧模擬邊更新DP值。

Top14????1397 找到所有的好字符串

https://leetcode.cn/problems/find-all-good-strings/

UP曾經嚴重高估的一道題。這道題目不用KMP也能通過，但實現極其易錯。在數位DP模板的基礎上，額外狀態定義是滿足當前長度k的后綴和evil長度k的前綴相同的最大k，這個狀態的轉移沒有那么顯然，如果不用KMP就需要對所有的可能轉移情況做預處理。

Top13????2060?同源字符串檢測

https://leetcode.cn/problems/check-if-an-original-string-exists-given-two-encoded-strings/

字符串壓縮碼由于長度大于9時截斷會出錯，這道題正確的狀態定義是s1的前i個字符，s2取前j個字符，同時有一個字符沒匹配上的字符數量是k（可以用k的正負性表示是哪邊沒匹配上），附加維度不可刪除。狀態轉移的細節也相當多。

Top12????913 貓和老鼠

https://leetcode.cn/problems/cat-and-mouse/

這道題用博弈論的DP做法不是特別難想，只是碼量大。但以本題的數據范圍，正確性可以保證的DP是會TLE的，比賽代碼幾乎都是錯誤的。本題的正解是拓撲排序，而即使競賽選手也往往會盡量嘗試讓DP能通過而不是完全更換思路，因此這道題目屬于VeryHard幾乎無爭議。

Top11????1728 貓和老鼠2

https://leetcode.cn/problems/cat-and-mouse-ii/

情況同913。但這道題更離譜的是，假設任意一方獲勝都不需要2次經過相同位置，而對步數設上限的做法沒有正確性，但8*8的棋盤內沒有反例。所以DP做法是否算正解至今仍有爭議。

Top10????1724 檢查邊長度限制的路徑是否存在2

https://leetcode.cn/problems/checking-existence-of-edge-length-limited-paths-ii/

1697的在線版本，但難度完全不是一個次元。這道題需要對基礎并查集模板的Union做改進，不能直接壓縮路徑，而是按秩序合并的同時，記錄每條邊的權重信息，查詢時如果某個合并方向的權重不滿足，就不能朝這個方向合并。

Top9? ?488 祖瑪游戲

https://leetcode.cn/problems/zuma-game/

這道題無論用BFS還是記憶化搜索，如果不剪枝會有極高的總TLE風險，但剪枝又極有可能剪掉最優解。具體剪枝操作應該是保證插入位置旁如果有同色球，那插入位置總是一串同色球之后的最后一個位置，AB之間插C的情況不必考慮，但AA之間插B的情況必須考慮。

Top8? ? 1531 壓縮字符串2

https://leetcode.cn/problems/string-compression-ii

壓縮字符串的題目往往難度很高，這道題的狀態定義很簡單，就是前i個字符拿掉j個需要的編碼長度。但是看上去無法狀態轉移，因為不可能枚舉所有包含s[i]的子序列。事實上對于每種字符，只需要考慮連續的位置，可以證明不連續的位置一定是其他狀態已經算過的。

Top7????1787 使所有區間的異或結果為零

https://leetcode.cn/problems/make-the-xor-of-all-segments-equal-to-zero

不難看出結果數組一定是長為k的周期數組，因此應當對k取模分組進行DP，并要求所有組修改成的值的異或和為0。但如果對每個狀態都枚舉修改成m需要的次數的所有合理的m，總復雜度肯定不允許。必須分析出哪些狀態不可能是最終答案，并將這些廢狀態都優化掉。

Top6????1977 劃分數字的方案數

https://leetcode.cn/problems/number-of-ways-to-separate-numbers

一個“非遞減”的限制讓這道題直接從水題變成主站難度分前10的變態題。狀態轉移方程看上去不算復雜，但如果暴力轉移，時間復雜度達到了n^3，必須注意到相鄰狀態有大量重復項，來用前綴和來優化。另外數字位數相同并不代表一定能轉移，數字位數相同時哪些能轉移是需要用LCP矩陣來預處理的。

Top5????1956 感染K種病毒需要的最短時間

https://leetcode.cn/problems/minimum-time-for-k-virus-variants-to-spread/

這道題需要數形結合思想，本質上求的是到k個點最大曼哈頓距離的最小時間，放在二維平面上就是找最小的包含k個點的傾斜45度的正方形。最大值最小化當然可以二分答案，但本題也可以用斜率±1的直線作為掃描線來找答案。

Top4????1982 從子集的和還原原數組

https://leetcode.cn/problems/find-array-given-subset-sums/

思路和2386題的略類似。首先要看出最小值和次小值之間一定是差了1個絕對值最小的元素，所有的元素可以根據是否有這個元素來分成長度相同的兩部分。但這個元素的正負性不能提前確定，即使用這個元素能分出兩部分，也不見得這個分法就是對的，所以需要一層層遞歸來尋找答案，直到只剩下1個0和1個非0值的2個元素，這才說明找到了答案。

Top3????1719 重構一棵樹的方案數

https://leetcode.cn/problems/number-of-ways-to-reconstruct-a-tree

這道題在周賽難度分top1呆了幾年，雖然這嚇人的難度分肯定是被兩個Medium影響了，但也是真的難。這道題破局的關鍵是父節點的鄰居數肯定不少于子節點，而根節點的鄰居數一定是n-1。所以應該先找到根節點，然后逐層向下建樹，子節點的鄰居一定是父節點的子集，否則就是非法；如果子節點的鄰居和父節點相同，就說明針對這對節點的構建方案不唯一，如果不存在非法，最終答案就是2。

Top2????2647 把三角形染成紅色

https://leetcode.cn/problems/color-the-triangle-red/

這是LCP戰隊賽第5題原題，被美國站抄來當了會員題。由于戰隊賽參賽者水平普遍高，而且給的時間也很充足，比賽期間還是通過了不少人的，但絕大多數人都是猜的解法，事實上如果面試中出現這道題，面試者是必須要證明4行一個周期的構造方案就是最優解，而這個證明方法是非常難想到的。

Top1????2699 修改圖中的邊權

https://leetcode.cn/problems/modify-graph-edge-weights/

這是目前整個主站的天花板。大思路是Dijkstra，但樸素的想法正確性是有問題的。這道題的正解有2種，一是先給定權重-1的邊的修改順序，然后二分猜讓最短路小于等于target需要改成1的最少的權重-1的邊數，如果有解且改完小于target就在最后的一條邊補差價。二是兩次dijkstra，第一遍默認所有-1都是1，從終點開始跑，第二遍則從起點開始跑，邊跑邊修改權重，并且保證改完之后還在最短路上。方法二思維難度遠遠超出了力扣的水平。

關鍵詞：