leetcode 第 420 场算法比赛

零、背景

这次比赛第三题题目有很大的歧义，题目求使数组非递减，我理解只要一个大于就满足非递减，结果一直不通过，被卡了很久。

A: 模拟。
B: 枚举 或 二分 或 滑动窗口。
C: 枚举。
D: 字符串hash。

排名：169
代码地址： https://github.com/tiankonguse/leetcode-solutions/tree/master/contest/4/420

一、出现在屏幕上的字符串序列

题意：键盘只有两个操作：1）追加一个字符a，2）最后一个字符加1。
求最少操作得到目标字符串。

思路：如果一个位置字符不是a，只能不断加1，直到满足。
所以可以循环所有位置，第一次插入a，之后不断加一，直到与目标字符相等。

二、字符至少出现 K 次的子字符串 I

题意：给一个字符串，问存在多少个子串，存在至少一个字母至少出现K次。

思路1：前缀枚举。

枚举每个位置为起始点的所有前缀字符串。
显然，前面的都不满足，一旦某个位置满足之后，后面的都满足。
满足个数是含满足位置之后的字符个数。

复杂度：O(n^2)

思路2：二分

预处理每个字符出现的位置列表。

a: a0,a1,a2,...
b: b0,b1,b2,...
...
z: z0,z1,z2,...

还是枚举起始位置，目标是求最短的满足 K 的前缀。
可以枚举 26 个字符，二分找到每个字母满足 K 个时的位置，从而可以找到最靠前的位置。

怎么二分呢？

假设当前起始位置是 P，判断的字母是 a。
首先二分查到位置 P-1 为止，字母a出现的个数 L。
然后查找字母 a 出现 L+K 次的位置，即 a[L+k]。

数组是位置列表，二分位置，根据偏移量即可计算出个数。

upper_bound(a.begin(), a.end(), P-1);

复杂度：O(n log(n))

思路3：打表

思路2是记录每个字母的位置列表。
如果把每个位置每个字母出现的次数都储存下来，则不需要二分，直接查表即可得到前缀出现的个数。

复杂度：O(26 n)

思路4： 滑动窗口

上一个位置找到了第一个满足要求的右边界。
下个位置的第一个满足要求的右边界肯定不会更小。
所以可以复用之前的结果。

删除上个位置后，怎么判断右边界之内是否满足答案呢？
统计数据时候，也统计满足要求的字母个数。
当删除上个位置后，个数由等于 K 个降低为 K-1个，则右边界肯定是不满足的，需要继续向后查找。

复杂度：O(n)

三、使数组非递减的最少除法操作次数

题意：给一个数组，每次操作，可以将一个位置的值修改为非1因子，问最少多少次操作可以将数组修改为非递减数组。

我理解的非递减数组是只要有一个位置后面的大于前面的，就算非递减。
结果这道题题的非递减指的是非递减有序。

另外，即使按非递减有序来做这道题，还有一个地方我看错题了。
题目说的是除以最大因子，而我看成除以任意一个因子了。
只是没想到比赛竟然也过了，尴尬。

先假设是除以任意因子，来看下怎么做吧。
显然需要动态规划。

对于一个位置的数字，不操作就是自身，操作是其中一个因子。
所以需要预处理求出所有因子。
求一个数字所有因子的复杂度为sqrt(n)。
求所有数字的复杂度就是 n sqrt(n)

之后可以使用动态规划来做这道题。

状态定义：

f(n,V) = F(n-1,V) 
f(n,v) = F(n-1,v) + 1
F(n,v) = min(f(n,i)), i<=v

f() 含义：如果第n个位置值为V，即是数字自身，则需要找到前一个位置值不大于 V 时的最优解。
如果第n个元素值小于V，即是数字的因子，则需要找到前一个位置不大于V时的最优解再加1。

F(v) 含义：所有不大于V的所有状态的最优解。

复杂度：O(n*V^2)

优化1：离散化
对于因数，只需要储存对应的位置偏移量。
一个数字的因数个数随着数字值的变大，个数与值的关系相差越大，大家可以按srqt(n)个来评估。

故这里就不需要枚举所有V，只需要枚举因子个数。
复杂度：O(n*V)

优化2：单调性
观察f(n,v)，可以发现随着 v 的增大，答案是递减的，即满足单调性。
故F(n,v)的答案是第一个不大于 v 的答案，可以二分来快速查找。
复杂度：O(n sqrt(V) log(sqrt(V)))

优化3：逆向递推
根据单调性的性质，最后一个数字必然选择自己，不会选择因数。
故可以倒推出，倒数第二个数字需要选择第一个不大于 v 的数字。
复杂度：O(n log(sqrt(V)))

再来看下正确的解法。

既然是除以最大因子，显然得到的就是最小非1因子，也就是最小素数因子。
所以预处理时，只需要保存最小素因子即可。

另外根据优化3，可以知道可以逆向递推的。
逆向递推时，就不需要二分查找了，直接判断即可。

预处理复杂度：O(n K)
递推复杂度：O(n)
K 为数据范围内素数的个数。

四、判断 DFS 字符串是否是回文串

题意：给一个有根树，按后序遍历得到一个路径，问每个子树的路径是否是一个回文串。

思路：字符串hash。

1）遍历得到路径时，顺便记录每个子树的路径区间。
2）求出每个子树路径区间的字符串 hash 值。
3）翻转路径，求出对应子树区间的字符串 hash 值，判断是否相等。

复杂度：O(n)

五、最后

这次比赛第三题看错题了，不然应该可以很快做出来。
第四题是字符串题，目前字符串题我都是字符串hash做的，其他算法我还不会。
后面有机会学习后，再单独出一篇文章介绍一下吧。

《完》

-EOF-

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