leetcode 第 301 场算法比赛 排名162/7129

零、背景

这次比赛差点翻车。
另外，第三题我转化为了一个面试题，大家可以看看会不会做。

一、装满杯子需要的最短总时长

题意：饮水机支持冷水、常温、热水三种温度类型的水。
同一时间可以装满两个不同类型的水或者装满一杯任意类型的水，且装满一次消耗一秒时间。
现在告诉你三个温度分别需要多少杯水，问至少需要多少时间才能装满所有杯子的水。

思路：

方法一：显然，每次选择杯子最多的那两个温度类型，答案会更优。

所以可以使用最大堆来做这道题。
每次选择最大的两个数，同时减一，大于0 的数字再次入队即可。

方法二：最理想情况下，每次都是装满两杯水，所以答案是 n/2 向上取整。

啥时候不能同时装满两杯水吗？
即有一个温度类型的杯数非常大，大于了其他两个杯子数量之和。

所以这里就可以分两种情况。

情况1：最大杯大于另外两个杯数之和，则答案是最大杯。
情况2：最大杯不大于另外两个杯数之和，则答案是所有杯之和除二向上取整。

二、无限集中的最小数字

题意：现在集合中有所有正整数，有两个操作。
操作1：删除一个集合中的最小数字，并返回。
操作2：向集合中加入一个数字。

思路：数据量不大，使用有序集合预先存在所有数字，按题意操作即可。

面试题扩展：假设数据范围很大，比如整数范围内。
每次删除的是指定数字，如果存在则删除，不存在返回-1。
又改如何做呢？

三、移动片段得到字符串

题意：给两个含LR_三种字符的字符串。
L 代表可以与左边相邻的_进行交换。
R 代表可以与右边相邻的_进行交换。
问第一个字符串是否可以通过交换得到第二个字符串。

思路1：

其实就是编译器中的语法分析，本质是状态机。

扫描的时候，遇到不相等则意味着后面移动交换可能会相等。
这种不相等的数据我们需要保存下，专业名称叫做状态。

之后再扫描的时候，遇到新的数据，状态会发生变化，称为转态转移。

对于这道题，可以划分为三个合法状态：相等、右移、左移。

三个状态的转移方程我们下面分别来讨论。

状态一：相等

这个状态是初始状态。

下一个数据相等时，则状态保持不变。

下一个数据，待处理字符是R，目标字符是 _时，进入右移状态，右移次数为1。
这个时候，状态可能是合法的。
比如待处理的下个字符是_，就可以通过一次交换，使得当前字符保持相等。

下一个数据，待处理字符是_，目标字符是L时，进入左移状态，左移次数为1。
这个时候，状态可能是合法的。
比如待处理的下个字符是L，就可以通过一次交换，使得当前字符保持相等。

下个数据是其他值时，则为进入非法状态，代表不匹配。

状态二：右移

待处理字符或目标字符，任意一个遇到L，则意味着状态非法，没有答案。

下个数据，待处理字符是R，目标字符是 _时，再次进入右移状态，右移次数加1。

下个数据，待处理字符是_，目标字符是R时，与右移状态相反，右移次数减1。
如果次数减为 0，则进入相等状态。

其他时候，意味着两个字符相等，状态保持不变。

状态三：左移。

左移状态的处理与 右移状态的处理相似，这里不再赘述。

扫描到最后，判断状态是否是相等状态即可。

方法2：贪心

先忽略_，判断只有LR时，字符串是否相等，不相等则意味着不匹配。

之后，扫描统计 LR分别出现的次数。

如果待处理字符串的R小于目标字符串的 R，则肯定没有答案。
因为针对这个前缀，待处理字符串的 R通过交换，只会越来越少。

同理，待处理字符串的L大于字符串的R，也肯定没有答案。
因为针对这个前缀，待处理字符串的L通过交换，只会越来越多。

上面两个规则始终满足时，最终答案也肯定是满足的（贪心核心）。

针对这个贪心核心我还没证明，你证明出来了吗？可以分享一下。

PS：又回顾了下状态机，发现状态机等价与这个贪心，那算是证明了。

四、统计理想数组的数目

题意：给一个正整数集合 [1,maxValue]，求构造一个长度为 n 的数组，要求数组的相邻数字满足后面的可以整除前面的数字。
问满足要求的数组个数有多少。

思路：n和maxValue的数据范围都是10^4，有点棘手。

由于最终是求数组的个数，那自然可以使用动态规划来做。

分解一：

面对这道题，先不考虑复杂度，可以把问题拆分为两步。
第一步：求出所有满足要求的数字不重复的序列。
第二步：对于每个序列，求出满足要求的数组个数。

假设已经求出一个满足要求的不重复的序列，长度为 k，则问题转化为了 k 个不同编号的苹果放进 n 个盒子里的组合数。

看到这个组合问题转化，我们可以发现对于一个不重复的序列，我们不关心序列的值，只关心序列的长度。
所以问题就可以进行简化。

分解二：

第一步：求出所有满足要求的、数字不重复、序列长度分别为[1,n]的序列个数。
第二步：对于每个序列长度，答案是一个序列数组个数 乘以 序列的个数。

再分析题目，发现倍数至少是 2，所以序列长度最长为 log(n)，按照题目的数据范围，长度不超过 15。

所以问题转化为了下面的样子。

分解三：

第一步：求出所有满足要求的、数字不重复、序列长度分别为[1,15]的序列个数。
第二步：对于每个序列长度，答案是一个序列数组个数 乘以 序列的个数。

那如何求出固定长度的序列个数呢？
没啥好办法，只能枚举所有起始位置，求出每个起始位置各个长度的个数，然后再聚合。

想到枚举起始位置时，可以发现，这个子问题又是一个动态规划问题。
起始位置依赖于下个位置的答案，然后进行聚合。

memset(dp, 0, sizeof(dp));
for(int now = maxVal; now >= 1; now--){
    dp[now][1] = 1;
    for(int i = 2; i * now <= maxVal; i++){
        for(int j = 1; j < 20; j++){
            dp[now][j + 1] += dp[i * now][j];
        }
    }
}

有了每个起始位置各个长度的个数，就可以聚合求出各个长度的总核数。

memset(nums, 0, sizeof(nums));
for(int now = maxVal; now >= 1; now--){
    for(int j = 1; j < 20; j++){
        nums[j] += dp[now][j];
    }
}

然后就是不同球放进盒子里(至少一个)的组合数了。

ans = 0;
for(int i = 1; i < 20; i++){
    ans += f(n, i);
}

对于球放盒子里至少一个的问题，一般需要转化为至少零个的组合问题。

f(n, i) = F(n-i, i);

球至少零个，就可以枚举哪些球至少一个，形成递归闭环。

for(k = 1; k <= i; k++){
    F(n, i) += f(n, k) * C(i, k);
}

复杂度分析：
求各个长度的个数：O(K * log(n))
之后的复杂度都不大于 O(n * log(n))

K = n/2 + n/3 + ... + n/n 
= n log(n)

故综合复杂度是 O(n * log(n)^2)

五、最后

这次比赛第一题可以贪心，我使用最大堆过的。
第二题我倒是通过暴力过的，不过可以扩展出一道面试题。
第三题我使用状态机过的，赛后看前几名都是贪心过的。
第四题则是很复杂的动态规划，多个动态规划套在一起使用，挺难的。

面试题扩展：假设第三题的数据范围很大，比如整数范围内。
并且每次删除的是任意指定的，如果存在则删除，不存在返回-1。
此时又改如何做呢？

加油，算法人。

《完》

-EOF-

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