leetcode 第 313 场算法比赛

零、背景

这次比赛前三题很水，第四题是个好题，本以为可以进入前 50 名，没想到这些人这么强。

一、公因子的数目

题意：给两个正数，求公因子数目。

暴力思路：数据量不大，枚举判断即可。
复杂度：O(n)

优化：先求最大公因数。
复杂度：O(n)
解释：极端情况下最大公因数是自身。

优化2：因数是对称出现的，只需要判断较小一半的因数。
复杂度：O(sqrt(n))
注意事项：n 恰好可以开方时，因子也是只能算一个。

二、沙漏的最大总和

题意：3*3 的小矩阵按照指定规则计算一个分数。
现在给一个大矩阵，问所有小矩阵里面，最大的分数是多少。

思路：枚举所有小矩阵，计算即可。

三、最小 XOR

题意：给两个数字 a 和 b，求一个数字 c。
使得 c 与 b的二进制 1 的个数相同，但是 c 与 a 异或值最小。

思路：想要 c 最小，从高到低，二进制中值为 1 的位数需要与 a 保持一致。

1）统计 b 二进制中 1 的个数。
2）如果 b 二进制 1 的个数不大于 a 的，从高到低消除 a 的高位二进制值为 1 的值即可。
3）如果 b 二进制 1 的个数大于 a的，则 a 的所有二进制 1 都需要消除，另外从低到高还要补充一些二进制 1。

复杂度：O(32)

四、对字母串可执行的最大删除数

题意：给一个字符串，可以按照下面两个规则删除字符串。

1）整个字符串删除。
2）如果字符串的模式是 a+a+b 三个字符串拼接而成，则可以删除一个 a 字符串。

问最多可以删除多少次才能把整个字符串删除。

思路：典型的动态规划问题。

定义状态：dp[i]，从 i 位置开始，后缀字符串的最优答案。

状态转移：

for(int l=1;l<=n;l++){
    if(s[i,i+l-1] = s[i+l, i+l+l-1]){
        dp[i] = max(dp[i], 1 + dp[i+l]);
    }
}

复杂度：O(n^3)

正常字符串判断是否相等的复杂度是 O(n)的。
而通过字符串 hash ，则可以在 O(1) 判断字符串。

预处理字符串，得到每个字符串前缀的 hash 值。
询问的时候，通过两个前缀值运算，从而得到任意子字符串的 hash 值，从而 O(1) 判断两个字符串是否相等。

复杂度：O(n^2)

另一个方法是预处理字符串，先求出所有相邻的相等的字符串。
实现方法：枚举相等的边界，左边从低位到高位计算hash值，右边从高位到低位计算hash只。

赛后看了大家的算法，发现还有另外两个做法。

一个是预处理出任意两个位置的 lcp，另外一个是套用后缀数组的模板。

最令人震惊的是，第一名使用暴力O(n^3)方法，竟然没有超时。

注意事项：运气不佳，原先使用10e7取模，竟然冲突了，后来又加了一个10e9才通过。

五、最后

这次比赛最后一题我想到的方法是字符串 hash，没想到做完后排名一百多名。

这道题能过这么多人我是没想到的，原来 leetcode 上的人也变得这么强了。

加油，算法人。

《完》

-EOF-

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