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，从终点开始跑，第二遍则从起点开始跑，边跑边修改权重，并且保证改完之后还在最短路上。方法二思维难度远远超出了力扣的水平。