leetcode 第 354 场算法比赛

零、背景

这次比赛质量比较高，都可以使用多种算法来解决。

一、特殊元素平方和

题意：给一个数组，问数组长度可以整除下标的元素的平方和。

思路：按题意循环判断，求和即可。

二、数组的最大美丽值

题意：给一个数组，数组的每个值 v 都可以修改为 [v-k, v+k] 中的任意一个值。
问如何修改，才能使得数组中相同值出现次数最多，输出这个最大次数。

思路1： 线段树
修改：每个元素的修改值对应一个区间，在线段树中区间加1。
查询：线段树查询区间最大值。
复杂度：O(n log(n))

思路2：差分。

预处理：在每个元素可以修改的最小值左边界加一，最大值右边界减一。
对所有边界排序，相同值时，左边界在前面。

计算：遍历所有边界，累计求和，取最大值。
复杂度：O(n log(n))

思路3：二分查找。

假设最终次数最多的相同值是 V，则 [V-k, V+k] 范围的值都可以通过修改得到值 V。
通过枚举左边界，可以计算出右边界，从而计算出相同值 V 的个数。

贪心：如果左边界不在输入的数组中，则可以选择大于左边界的最小输入元素来当做左边界。

计算：输入数组排序，枚举左边界，二分查找右边界，从而可以计算相同值的个数。
复杂度：O(n log(n))

思路4：双指针
二分查找每次是独立查找右边界的。
其实可以利用上次查找的信息，即双指针。
复杂度：O(n log(n))

三、合法分割的最小下标

题意：给一个数组，问是否可以拆分为前后两个数组，使得两个数组都存在支配元素且相同。
支配元素：出现次数最多的相同元素个数乘以2大于数组大小。

思路1：枚举。
维护一个支持增删的统计每个元素对应次数以及次数对应元素集合的数据结构。
按照题意，从左到右依次更新两个数据结构，判断是否满足答案即可。

思路2：统计。
输入的数组也存在支配元素，可以证明，答案的支配元素肯定与输入的支配元素相同。
所以可以先计算输入的支配元素，然后循环数组，可以统计到支配元素在左边的个数，判断是否满足要求。

四、最长合法子字符串的长度

题意：给一个字符串 s 和一个字符串集合 S ，求一个子字符串 ans ，使得字符串集合 S 中任何一个字符串都不是子字符串 ans 的子串。

分析：假设第一个与集合匹配的起始位置时 i，匹配长度是 l， 则可以得到几个结论：

1）前缀 s[0:i-1] 肯定是答案，因为第一个匹配的位置是 i。
2）前缀 s[0:i+l-1] 肯定不是答案，因为s[i,i+l-1]在集合中。
3）前缀 s[0,i+l-2] 可能是答案，需要判断 s[i,i+l-2] 是否有子串在集合中，即找到最长的s[i,k]，使得子串不在集合里。

基于这个推论，可以使用下面几个方法来解决这个道题。

思路1：trie 树+双指针。

字符串集合构造 trie 树。
循环枚举 s 某个位置为起始位置时，检查是否有某个前缀在字符串集合中。
如果不在集合里，则当前位置可以当做答案前缀的一部分。
如果在集合里，假设匹配的是 s[i,i+l-1]，则枚举s[i,i+l-1]的所有后缀，找到最长的s[i,k]，使得子串不在集合里。

复杂度：O(n * L * log(L))
L 不大于 10，故不会超时。

思路2：动态规划。

如下图，枚举每个位置，预处理出每个位置开始的最短前缀，使得这个前缀在集合里，如果不在，则只为字符串的长度。

之后从后到前处理，计算出每个位置为前缀，子串匹配的最短前缀dp[i] = min(dp[i], dp[i+1])。
有了子串首次匹配的位置，长度减一，既可以保证子串都不在集合里。

复杂度：O(n * L)

思路2：hash+双指针。

与trie 树类似，既然字符串集合中每个字符串都不长，直接 hash 储存，通过枚举来判断是否存在前缀在集合即可。

五、最后

这次比赛除了第一题，后面三题都有多种不同的解法。
第二题有 4 种解法：线段树、差分、二分查找、双指针。
第三题有 2 种解法：枚举、统计。
第四题有 3 中解法：trie树+双指针、动态规划、hash+双指针。

你都是怎么做这些题呢？

《完》

-EOF-

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