leetcode 第 346 场算法比赛

零、背景

这次比赛最后一题是图论，我想着暴力会超时，在想非暴力方法，最终没做出这道题。

赛后看了前几名的代码，大多数都是暴力过的，但是有个人的算法非常巧妙。

一、删除子串后的字符串最小长度

题意：给一个字符串，不断的删除AB和CD子串，求删除后剩余的最短串。

思路：维护一个栈，贪心，能删除则删除。

二、字典序最小回文串

题意：给一个字符串，最小修改次数可以使字符串成为回文串，问最小修改下得到的字典序回文串。

思路：双指针向中间扫描，如果对称位置不相等，都赋值为较小的那个。

三、求一个整数的惩罚数

题意：求小于等于 n 的所有惩罚数的平方和。
惩罚数：数字 p 平方的某个子串拆分之和等于当前数字 p。

思路：预处理，判断所有数字是不是惩罚数。

判断方法：动态规划。

状态定义：dp[a][b] 数字 b 的子串拆分是否可以得到数字 a。

递推空间复杂度：O(1000^3)
递归空间复杂度：远远小于O(1000^3)，实际是4100个状态。

所以使用map<pair<n,nn>, ans> 来记录状态，即不会超时与 OOM。

状态转移：枚举字符串的后缀，判断剩余的前缀和剩余的数字和是否有答案。

四、修改图中的边权

题意：给一个 无向带权连通 图，其中权值为 -1 的边为魔法边，权值可以修改为任意正整数。
问怎么修改才能得到 S 到 D 的最短路为 T 的图。
输出所有的边和修改后的权重值。

思路：在 Leetcode 上算比较难得一类题。
之所以难，不是因为算法难，是 Leetcode 上图论题比较少，大家都生疏了。

看了前几名的代码，前三名都是贪心暴力做的，只有一个人算法非常优雅，下面来看看吧。

首先可以明确，有两种情况肯定是没答案的。

不使用魔法边，最短路小于 T，则没答案。
使用魔法边，权值按 1 处理，最短路大于 T， 则也没有答案。

算法1：枚举魔法边+BF算法

所有魔法边从图中删除，然后 BF 算法预处理求任意两个顶点之间的最短路。
复杂度：O(n^3)

之后枚举魔法边，判断加入当前魔法边是否可以得到答案。
如果可以得到答案，则剩余的魔法边全部设置为无穷大。
如果不能得到答案，则当前魔法边权值设置为 1，加入到图中，执行 BF 容斥。

综合复杂度：O(n^3) + O(E * n^2)

这个复杂度最坏有 O(n^4)，即10^8。

总结下这个算法。
假设在第 i 个魔法边找到答案，则
[0, i-1] 魔法边的权值都是 1.
[i,i]的魔法边是动态计算出来的。
[i+1,e-1]的魔法边的权值值都是无穷大。

第一名这样做的，没有超时。

算法2：每局魔法边+dijkstra算法

所有魔法边从图中删除，求 dijkstra 单源最短路。

与算法1整体思路类似，这里每次加入权值为 1 的魔法边后，都需要求一次 dijkstra 最短路。
如果发现加入之后最短路小于目标了，即找到答案。

总结下这个算法，与算法1一模一样。
假设在第 i 个魔法边找到答案，则
[0, i-1] 魔法边的权值都是 1.
[i,i]的魔法边是动态计算出来的。
[i+1,e-1]的魔法边的权值值都是无穷大。

这个是第二名的算法。

算法3：二分魔法边的最大值

二分魔法边的总权值之和，然后判断是否有答案。

判断方法：魔法边的权值平均分配的， 如果无法整数，则剩余的平摊给最前面的魔法边。

假设在第 i 个魔法边找到答案，则
[0, x] 魔法边的权值都是 tms.
[x+1,e-1]的魔法边的权值值都是 tms+1。

复杂度：O(n^2 log(K))

这个算法不会超时，但是正确性我无法证明，甚至我怀疑存在反例。

这是第三名的算法。

算法4：两遍 dijkstra

算法1和算法2的优化版本，思路一样，但是复杂度很低，很巧妙的算法。

第一遍 dijkstra 魔法边权值都按 1 处理，求出单源最短路。
并计算出最短路与目标的差值 diff。

第二遍，每轮找到一个最小顶点后进行容斥时，对魔法边特殊处理。
特殊处理：参考第一轮当前节点的最短路值，当前魔法边补齐差值，使得第二轮的最短路与第一轮最短路的差值是 diff。

复杂度：O(n^2)

这是第四名的算法。

五、最后

这次比赛最后一题还是比较难的。

不过看了第四名的代码，发现这道题还是很有意思的。
建议大家都去研究下这道题。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code