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

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

Top30????1595 連接兩組點(diǎn)的最小成本

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

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

Top29????1494 并行課程II

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

這道題目的零神大數(shù)據(jù)難度分不高，是因?yàn)楸荣惼陂g絕大多數(shù)通過的代碼都是錯(cuò)誤的貪心。本題用拓?fù)渑判蚴遣煌ǖ?，正解?yīng)該是狀態(tài)壓縮DP。對(duì)于每一種狀態(tài)，都需要枚舉接下來可以學(xué)的課程的所有不超過k門的組合，如果實(shí)現(xiàn)有漏洞，很容易TLE。

Top28? ? 2281 巫師的總力量和

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

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

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

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

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

Top26????420 強(qiáng)密碼檢驗(yàn)器

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

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

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

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

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

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

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

這道題的零神大數(shù)據(jù)難度分不是特別離譜，是因?yàn)榱燮脚_(tái)比賽期間可以看WA的case。找最大的環(huán)確實(shí)沒錯(cuò)，但答案還有另一種可能，就是一對(duì)戀人坐在一條長鏈上。

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

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

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

Top22????2573 找到對(duì)應(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的方法去完整驗(yàn)證更是大多數(shù)人難以直接想到的，之所以需要驗(yàn)證是因?yàn)闃?gòu)造的過程沒有利用LCP的所有性質(zhì)。大部分比賽代碼都被rejudge沒了，即使放到CF里如果必須驗(yàn)證的數(shù)據(jù)都在system test里，難度分也不太會(huì)低于2000。

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

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

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

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

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

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

Top19????803 打磚塊

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

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

Top18? ? 546 移除盒子

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

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

Top17????818 賽車

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

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

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

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

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

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

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

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

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

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

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

Top13????2060?同源字符串檢測(cè)

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

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

Top12????913 貓和老鼠

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

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

Top11????1728 貓和老鼠2

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

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

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

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

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

Top9? ?488 祖瑪游戲

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

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

Top8? ? 1531 壓縮字符串2

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

壓縮字符串的題目往往難度很高，這道題的狀態(tài)定義很簡單，就是前i個(gè)字符拿掉j個(gè)需要的編碼長度。但是看上去無法狀態(tài)轉(zhuǎn)移，因?yàn)椴豢赡苊杜e所有包含s[i]的子序列。事實(shí)上對(duì)于每種字符，只需要考慮連續(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)對(duì)k取模分組進(jìn)行DP，并要求所有組修改成的值的異或和為0。但如果對(duì)每個(gè)狀態(tài)都枚舉修改成m需要的次數(shù)的所有合理的m，總復(fù)雜度肯定不允許。必須分析出哪些狀態(tài)不可能是最終答案，并將這些廢狀態(tài)都優(yōu)化掉。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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