leetcode 第 415 场算法比赛

零、背景

这次比赛第三题和第四题一样，只是数据范围的差异。
第三题我使用 O(n^2) 的复杂度一直超时 或者 WA，最后加了一个函数优化才通过。

A: 面试题。
B: 简单动态规划。
C: HASH + 动态规划。
D: hash或Z函数或AC自动机 + 动态规划。

排名：200+
代码地址： https://github.com/tiankonguse/leetcode-solutions/tree/master/contest/4/415

一、数字小镇中的捣蛋鬼

题意：给一个大小为 n 的数组，值域为 [0,n-1]。
现在有只有两个数字都出现两次，其他数字出现一次，问出现两次的数字的值。

思路：

方法1：排序
方法2：hash
方法3：原地交换，面试时希望得到这个方法。
原地交换的代码参考 A_swap.cpp

二、最高乘法得分

题意：给一个大小为4的数组和大小为 n 的数组，求在第二个数组中挑 4 个元素（相对顺序不变），与第一个数组求叉乘。
叉乘定义: (a0,a1) X (b0,b1) = a0*b0 + a1*b1

思路：动态规划。

定义状态：f(n,m) 第一个数组前 n 个元素 与第二个数组前 m 个数组匹配叉乘后的最优解。

状态转移方程：
分为最后一个元素匹配或不匹配，不匹配时第二个数组删除最后一个元素。

f(n,m)=max(f(n-1,m-1), f(n, m-1))  

复杂度：O(nm)

当然，这个状态转移方程可以写成递推的方式，从使用滚动数组来节省内存。
滚动数组的代码参考：B_loop.cpp

三、形成目标字符串需要的最少字符串数 I

题意：给一个字符串数组和目标字符串 s，问字符串数组里面最少可以选择多少个前缀，才能组成目标字符串。

思路：动态规划。

状态定义：f(n) 目标字符串前n个字符最少需要多少个前缀才能组成答案。

状态转移方程：
枚举所有后缀，判断是否可以选择。

f(n) = min(1 + f(i-1)) & exist(s[i,n])  

判断后缀是否存在可以使用hash来优化。
预处理所有前缀，储存在 hash 表中。
对于子串s[i,n]的hash，可以通过前缀求差快速得到。

复杂度：O(n^2)

比赛的时候，直接这样写超时了。
我做了一个常数优化通过了这道题。

比赛期间遇到不少坑。

坑1：模 mod1e7 遇到 hash 冲突问题。
坑2：样例卡常数。

优化1: 换成 mod1e9 依旧冲突。

优化2: 换成 mod1e7 与 mod1e9 的组合，超时。

优化3: 字符串数组只需要求前 n 个前缀，依旧超时。

优化4：预先设置 hash 的桶大小，依旧超时。

优化4：字符串只有100个，定义 n 个 hash ，每个 hash 大小 100.
比赛的时候，我是通过这个优化通过这道题的。
分n个hash的代码参考：C.cpp

优化5：前缀一旦不匹配，后面的都不匹配，终止。
评论：优化只是提高性能，意外的降低了冲突的概率，从而通过这道题。
不过这个是我比赛后试出来的。
代码：C_hash.cpp

四、形成目标字符串需要的最少字符串数 I

题意：给一个字符串数组和目标字符串 s，问字符串数组里面最少可以选择多少个前缀，才能组成目标字符串。

思路：和第三题一样，数据范围增加一个数量级。

第三题的状态转移方程需要调整下，修改为后缀。

状态定义：f(n) 目标字符串从第n个字符开始的后缀字符串的最优答案。

状态转移方程：

f(n) = min(1 + f(i+1)) & exist(s[n,i])  

方程转化一下等价与下面的形式。

l = max(i) && exist(s[n,i]);
f(n)= 1 + min(f(n+1), f(n+2), ... f(i+1));

如果可以快速的找到边界 l 以及 可以快速查询区间 [n+1, i+1] 的最小值，就可以做这道题了。

根据 l 的性质，满足左边都存在，右边都不存在，故可以二分查找。
而区间最值，则可以使用线段树来做。
复杂度：O(n log(n))
代码： D_hash.cpp

其实，这道题是字符串题，可以使用标准的字符串算法来解决。
例如可以使用 Z函数来快速计算出匹配的后缀，从而可以代替二分快速计算出上面的 l。
代码参考：D_z_function.cpp

还有人使用AC自动机来做，这个算法最坏情况下复杂度会退化为树高，是否会超时我没去研究，有空了研究下。

五、最后

这次比赛最后一题是字符串题。
我之前字符串题做的比较少，对我来说是比较难的。

不过如果第三题没有被卡常数，第四题我同样会使用 hash 的方法代替朴素的字符串算法。

《完》

-EOF-

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