leetcode 第 377 场算法比赛

零、背景

周六科目二成功考试通过，周日科目三预约的是下午练车，所以上午有时间参加比赛。

这次最后一题是和综合题，但是总体复杂度不高，但是不知为啥总是超时。

A: 排序
B: 预处理垂直线，枚举水平线
C: 全源最短路。
D: hash+全源最短路。

比赛代码:
https://github.com/tiankonguse/leetcode-solutions/tree/master/contest

一、最小数字游戏

题意：两个人轮流做游戏，每一轮A和B依次移除最小数字，然后B和A依次把数字追加到数组中。

思路：排序，交换相邻数字即可。

二、移除栅栏得到的正方形田地的最大面积

题意：给一个矩阵，现在告诉你若干水平线和垂直线，问是否可以删除一些水平线和垂直线，让剩下的线构成至少一个正方形。
如果可以，返回最大的正方形面积。

思路：如果可以构成正方形，肯定需要两根水平线和两根垂直线。
所以需要枚举两根水平线和两根垂直线。
复杂度：O(n^4)

优化1：上面枚举没有利用正方形的性质。
两根水平线确定后，正方形的边长就确定了。
所以只需要再枚举一根垂直线，另一根垂直线的位置就确定了（上下两个可能）。
复杂度：O(n^3)

优化2：确定正方形边长时，能不能直接判断是否有垂直线答案呢？
预处理垂直线，记录所有可能的边长，即可直接判断。
预处理复杂度：O(n^2)
枚举复杂度：O(n^2)

三、转换字符串的最小成本 I

题意：给一个字符映射到另外一个字符的代价，问原始字符串是否可以替换为目标字符串，求最小代价。

思路：字符只有26个，合并输入映射，可以得到26个字母之间的输入映射代价。
然后通过 floyd 求全源最短路，即可以得到任意两个字母之间的最小映射代价。
复杂度：O(26^3)

之后判断输入字符串是否可以转化为目标字符串即可。

四、转换字符串的最小成本 II

题意：给一个字符串映射到另外一个字符串的代价，问原始字符串是否可以替换为目标字符串，求最小代价。
规则：原始字符串到目标字符串的映射过程中，映射的子串之间不能有交集（相等除外）。

思路：第三题的升级版本。

第一步：对映射的字符串进行hash处理，转化为数字之间的映射，并求全源最短路。
复杂度：O(200^3)

第二步：对原始字符串和目标字符串的所有子串进行预处理，求出对于的hash值。
复杂度：O(1000^2)

第三步：动态规划，枚举判断原始字符串后缀是否可以替换到目标字符串后缀。
方程：dp[i] = min(dp[j-1] + cost[fromHash][toHash] )
复杂度：O(1000^2)

就是这样一个算法，竟然超时了。

全源最短路的复杂度最高。
由于边数最多只有 200 个，于是我不适用 floyd， 改成求每个顶点的最短路。
但源最短路使用 SPFA 堆优化。
复杂度：O(200^2)

最终复杂度：O(1000^2)
但还是超时了。

我把所有 vector 由临时变量调整为全局数组，结果还是超时了。

五、最后

这次比赛最后一题被卡了，看其他人没有使用 hash 字符串，使用二分查找或者 tire 树来做的。
其实 hash 的速度更快，只开了两个O(1000^2)的内存，其他的都是O(200^2)的内存，最终却超时了，莫名其妙。

《完》

-EOF-

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