leetcode 第 291 场算法比赛

零、背景

由于五一要值班，我便抽时间做了下四道题，都不难，但是我被卡超时了。

一、移除指定数字得到的最大结果

题意：给一个字符串，问删除一个指定值的字符后，可以得到的最大字符。

思路：扫描所有位置，值是目标值时，通过 substr 得到前后缀拼接处字符串，更新答案即可。

小提示：直接使用 erase 删除指定位置字符更方便。

二、必须拿起的最小连续卡牌数

题意：给一个数组，求最小的子数组，使得数组中至少有一个数字出现两次。

思路：map 记录每个数字最后一次出现的位置。
扫描数组时，先通过当前值与最后一次出现的位置形成一个满足要求的子数组，更新答案。
然后更新当前值最后一次出现的位置即可。

三、含最多 K 个可整除元素的子数组

题意：给一个数组，问最多含 K 个整数 P 的子数组，去重后有多少个？

思路：数据量不大，暴力做大，就是求所有满足要求的子数组，set 去重即可。

暴力做的复杂度比较高，我以为 leetcode 会卡超时，所以就使用 hash 的方法做了。

hash 方法：每个满足要求的子数组可以按照 N 进制数字，计算出一个很大的值，再模上一个很大的质数即可代表这个子数组。
第一次我使用一个 HASH 错误一次，改成双 HASH 后就通过了。

LCP 方法：枚举一个子数组时，判断当前子数组在之前的子数组是否出现。

四、字符串的总引力

题意：给一个字符串，每个子字符串出现的不同字符个数称为引力值。
求所有子字符串的引力值之和。

思路：

我第一时间想到的是动态规划。

一个字符串，出现的字符可以使用 bit 位标示，26 个字母，顶多 26 位。

对于某个位置的所有后缀字符串，顶多只能有 26 个不同的 bit 位组合。

定义状态 f(i, b) 代表第 i 个位置为结尾的后缀字符串中，bit 位值是 b 的个数。

则可以得到下面的转移方程：f(i+1, i|1<<v) += f(i, b)。
答案是累加 f(i, b) * __builtin_popcount(b)

复杂度：O(26n)

没想到这个复杂度提交后超时了，我便把 map 改成 unordered_map 还是超时了。
__builtin_popcount 去掉，还是超时了。

最终改成 vector，然后使用 O(26*26*n)的复杂度去重，没想到又过了。

赛后看题解，发现可以通过枚举的方法来计数计算出答案。

对于包含一个字符的所有子字符串，可以按照字符首次出现的位置，对这种子字符串进行分组。
理由也很简单，一个字符串中这个字符出现多次，只能算一个引力值，那就可以算在第一次出现的那个位置上。

这时候就可以发现一个规律。

假设字母某次在 x 位置出现，接着在 y 位置出现，则以 y 位置首次出现的子字符串的规律如图。

在 (x, y] 之间为前缀，且前缀包含位置 y 的所有字符串，都是满足要求的字符串。
这样的字符串个数也可以计算出来，为(y-x) * (n-y)。

所以，统计每个字符出现的位置列表，循环计算出答案求和即可。

五、最后

这次比赛，第三题暴力可以做，我怕超时，使用双 hash 的方式过的。
第四题使用 O(26 n) 的复杂度超时了，改成 O(26 * 26 * n) 的复杂度才通过，神奇。

加油，算法人。

《完》

-EOF-

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