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

(相關(guān)資料圖)

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

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

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

這道題首先要做一個思維轉(zhuǎn)換，題意是要求cost矩陣中選取一些元素，且每行每列都必須有元素入選，求所選元素最小值?？雌饋硎且坏篮苈愕臓顟B(tài)壓縮DP，但每行并不一定只選1個元素最優(yōu)，為了能在合理的時間復(fù)雜度內(nèi)考慮到每行選多列的情況，就需要在同一行內(nèi)狀態(tài)轉(zhuǎn)移。

Top29????1494 并行課程II

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

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

Top28? ? 2281 巫師的總力量和

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

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

Top27????480 滑動窗口中位數(shù)

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

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

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

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

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

Top25????2071 你可以安排的最多任務(wù)數(shù)目

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

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

Top24????2127 參加會議的最多員工數(shù)

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

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

Top23????2499 讓數(shù)組不相等的最小總代價

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

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

Top22????2573 找到對應(yīng)LCP矩陣的字符串

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

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

Top21????2386 找出數(shù)組的第K大和

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

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

Top20????1330 翻轉(zhuǎn)子數(shù)組得到最大的數(shù)組值

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

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

Top19????803 打磚塊

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

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

Top18? ? 546 移除盒子

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

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

Top17????818 賽車

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

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

Top16????964 表示數(shù)字的最少運算符

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

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

Top15????1896 反轉(zhuǎn)表達式值的最少操作次數(shù)

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

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

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

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

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

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

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

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

Top12????913 貓和老鼠

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

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

Top11????1728 貓和老鼠2

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

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

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

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

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

Top9? ?488 祖瑪游戲

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

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

Top8? ? 1531 壓縮字符串2

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

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

Top7????1787 使所有區(qū)間的異或結(jié)果為零

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

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

Top6????1977 劃分數(shù)字的方案數(shù)

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

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

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

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

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

Top4????1982 從子集的和還原原數(shù)組

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

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

Top3????1719 重構(gòu)一棵樹的方案數(shù)

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

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

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

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

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

Top1????2699 修改圖中的邊權(quán)

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

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

關(guān)鍵詞：