leetcode 第 396 场算法比赛

零、背景

这次比赛在节假日最后一天，最后一题很有难度。

A: 字符统计。
B: hash统计。
C: 枚举+统计前缀和。
D: 贪心枚举。

排名：无
代码地址： https://github.com/tiankonguse/leetcode-solutions/tree/master/contest/3/396

一、有效单词

题意：给一个字符串，问是否是有效单词。

有效单词定义：
1）长度至少为 3
2）有字母或者数字组成
3）至少包含一个元音字母
4）至少包含一个辅音字母

思路：枚举判断每一个字符是否是字母数字，并统计是否出现元音和辅音即可。

二、K 周期字符串需要的最少操作次数

题意：给一个k个子串，每次可以选择一个子串替换另外一个子串，问至少替换多少次才能使得所有子串相等。

思路：显然是用出现次数最多的子串替换其他子串，统计每个子串出现的次数即可。

算法：使用 字符串 hash 来高效统计。

hash算法模板：https://github.com/tiankonguse/leetcode-solutions/blob/master/doc/string/hash.cpp

三、同位字符串连接的最小长度

题意：给一个字符串，求长度最小的同位子串。

同位子串定义：同位子串拼接组成原字符串。

思路：从小到大枚举同位子串的长度，判断是否是答案。

判断：同位子串长度固定后，通过前缀字符个数差判断是否所有子串是否相等。

复杂度：O(n/1+n/2+n/3+...)=O(nlogn)

证明：https://en.wikipedia.org/wiki/Harmonic_series_(mathematics)#Partial_sums)

四、使数组中所有元素相等的最小开销

题意：给一个数组，选一个数字加1代价为 cost1，选两个不同位置数字分别加1代价是 cost2，求使所有数字相等的最小代价。

思路： 显然，cost1*2<=cost2时，都选择操作一个数字最优。

其他情况，如果存在多个数字都不是最大值，则选择若干个操作2，可以得到更优的答案。

可以证明，保持最大值不变的情况下，每次选择最小的两个数字加1(操作2)，答案是更优的。
这样操作下去，就会只剩下一个数字不是最大值。
模拟复杂度：O((n*maxVal-sum) * log(n))

优化：什么情况下只会剩下一个数字不是最大值呢？
只有一种情况：最小值非常小，与其他非最大值全部匹配后，还有剩余。
其他情况，不考虑奇偶性的话，可以两两匹配，使得所有数字都与最大值相等。

条件：2*(maxVal-minVal) > n*maxVal-sum
我们可以根据上述条件，直接计算得到剩余一个数字与最大值的差距。
优化复杂度：O(n)

此时，有三种策略：
1）最后一个非最大值全部选择代价 1。
2）当前最大值上限加1，继续贪心选择，直到所有值相等。
3）最后一个数字进行 k 次策略1，剩下的贪心进行多次策略2。

可以发现，此时我们只关心最大值与最小值的差值，用 d 表示。

策略1的成本是：f1(d)=d*cost1

策略2的成本推导如下：
假设增加 x 层使得所有值相等，则需满足公示 d+k <= x*(n-1)。
从而推导出 x=d/(n-2)。
成本为 f2(d) = (x*n+d)/2 * cost2

策略3的成本是: f3(d)=k*cost1 + f2(d-k)

由于不知道哪个策略是最优的，最简单的方法是策略3 枚举所有的 cost1 的个数，取最小值。
第二阶段枚举复杂度：O(n)

枚举优化：
如果枚举 cost1 的次数，策略2的公式比较复杂，不好优化。
换成枚举增加的层数 x，优先进行贪心操作2，剩余的全部操作1，则公式会变得简单清晰。

如果 d+x <= x*(n-1), 则可以进行(d+x+x*(n-1))/2次操作2，考虑奇偶性，可能有一个进行操作1。
否则，进行 x*(n-1) 次操作2，进行 d+x - x*(n-1) 次操作1。

这个分情况讨论，在数学上是分段函数，可以发现 x 比较小时，曲线是递减的，x 比较大时，曲线是趋势递增的。
什么是趋势递增呢？就是微观非递增，宏观递增。
为什么会这样呢？因为奇偶性的计算方法不一样。

所以，面对这种情况，需要分奇偶性讨论。
分了奇偶性，曲线就严格遵循先递减，再递增了。

对于先递减再递增的曲线，典型的做法是三分，从而可以把复杂度降到 O(log(n))。

三分优化：其实公式确定了，我们可以直接分奇偶性推导出公式的最值。
边界其实就是 d/(n-2)，在前面的策略2时提到过。
这样复杂度就可以降低到 O(1)

当然，比赛过程中不建议大家这样做，因为这样做存在边界问题。
比如可能整除问题，加1或者减1可能才是最优值，处理不好就会不断地 WA 了。

五、最后

这次比赛最后一题比较难，可以枚举，也可以三分，也可以直接计算答案。
你是使用什么算法做的最后一题呢？

《完》

-EOF-

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