leetcode 第 368 场算法比赛

零、背景

这次比赛第三题有暴力方法没敢写，先做第四题动态规划。
最后做第三题时，想着先使用暴力方法试试，结果一下就过了。

一、元素和最小的山形三元组 I

题意：给一个数组，问是否存在三元组，中间的大于两边的，存在时返回和最小的三元组。

思路：暴力枚举。
复杂度：O(n^3)

二、元素和最小的山形三元组 II

题意：给一个数组，问是否存在三元组，中间的大于两边的，存在时返回和最小的三元组。

思路：与第一题的题意一样，不过这里数据量比较大，不能枚举。
由于是寻找两边都小于中间的三元组，枚举中间的值，找两边最小的值即可。

预处理每个位置两边的最小值，即可判断每个位置是否可以组成三元组的中间值。
复杂度：O(n)

三、合法分组的最少组数

题意：给一个数组，要求对数组进行分组，每组的值都相等，且任意两组的元素个数差值不大于1。
求最小分组。

思路：

第一步：值统计。
题目要求分组内值相等，所以我们不关心值，只关心相等值的个数，统计相同值出现的次数。
复杂度：O(n)

第二步：次数统计。
值出现相同次数时，进行的分组策略肯定是一致的，所以每个次数只需要保留一个，计算出答案后，乘以次数的频率即可。
复杂度：O(n)

第三步有两种方法。

方法一是暴力枚举分组大小 [a,a+1]。
每个次数按这个分组大小进行划分，最终求和，后面介绍怎么公式O(1)计算一个次数的划分。
复杂度：O(n sqrt(n))

推导：枚举分组大小时，只需要枚举出现的最大次数。
故复杂度为 O(最大次数 * 次数个数)

假设有一个数字出现n/2次，其他数字分别出现1,2,...,sqrt(n/2)次，则最大次数为n/2，次数个数为sqrt(n/2)。
复杂度为 O(n/2 * sqrt(n/2))
去掉常数，复杂度即为 O(n sqrt(n/2))。

方法二是集合合并。

先预处理计算每个次数可以划分哪些有效的分组，记录在集合里。
不同次数最坏情况有 O(sqrt(n)) 个，所有次数从小到大遍历一遍，累计需要O(n)次。
故复杂度为O(n)

所有次数都这样计算后，出现在所有集合里的有效分组才可能是答案，所以需要对这些分组进行集合统计。
由于是取交集，收敛的会很快，但是复杂度无法计算。
但是可以评估综合复杂度：次数 * 集合交集
由于集合交集不大于最小集合大小，故复杂度小于O(n)

有了有效分组，计算每个分组的答案即可。

计算具体一个分组的答案：

假设次数时 k, 分组大小为 [a,a+1]，先记录两个公式。
a+1 的个数记为 b=k / (a + 1)。
a+1 的余数记为 c=k % (a + 1)。

则有两种情况是没有答案的

情况1：k<a。
情况2: c > 0 && a - c > b
解释：如果有余数 c，通过a+1让出一个1，看是否能把 c 构造为 a。

有答案时，如果没有余数，答案就是 b，有余数了，答案就是 b+1。

四、得到 K 个半回文串的最少修改次数

题意：给一个字符串和k，问将字符串划分为k 个子字符串，且每个子字符串修改为半回文串 的最小修改数。

思路：动态规划。

状态：f(n,k) 前 n 个字符划分为 k 个子串的最优答案。
方程：f(n,k) = min(f(n-i,k-1) + f1(n-i+1,n))
解释：枚举最后一个子串，分别求前面状态的答案和最后一个子串的答案，求和。

子串的答案可以通过动态规划预处理得到。
状态：f1(l,r) 字符串s[l,r]的答案。
方程：f1[l,r] = min(f2(l,r, d))
解释：枚举所有余数，计算答案。

每个数字的余数，也可以预处理得到。
每个子串与余数的答案，可以扫描一遍计算出答案。

综合复杂度不好计算。
子串拆分复杂度： O(n^2)
余数预处理复杂度: O(n^2)，每个数字余数约为 ln(n) 个。
子串的答案复杂度: O(n^3 ln(n))
综合复杂度为O(n^3 ln(n)) 。

当然，动态规划采用递归实现时，因为有很多非法状态，复杂度远远比这个小。

五、最后

这次比赛没想到能进前百名。
第三题一开始暴力枚举没敢写，毕竟最坏情况下是 O(n sqrt(n/2))的复杂度，没想到一下就通过了，当然我也补充了标准的集合合并的方法。
第四题则是比较综合的动态规划，涉及到多个不同状态的结合来解决这道题。

《完》

-EOF-

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