LeetCode周赛301，离大谱，手速场掉分，质量场掉大分……

大家好，我是梁唐。

今天是周一，我们来看下昨天的LeetCode周赛。

这一次是周赛第301场，这一场由中国银联赞助。前500名都有内推的机会，离谱的是老梁我刚好第502名……

这一次的题目质量不错，比之前提升了不少。个别题目还是有一定难度，虽然没有用到高端的算法，但是需要仔细思考才能想出解法。非常适合大家练习。

比赛结束之后看到评论区里有人吐槽，把我逗得不行……

好了，闲言少叙，进入正题，来看看这次的赛题吧。

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

现有一台饮水机，可以制备冷水、温水和热水。每秒钟，可以装满 2 杯 不同 类型的水或者 1 杯任意类型的水。

给你一个下标从 0 开始、长度为 3 的整数数组 amount ，其中 amount[0]、amount[1] 和 amount[2] 分别表示需要装满冷水、温水和热水的杯子数量。返回装满所有杯子所需的 最少 秒数。

题解

怎么样，第一题是不是就来了个下马威？

看着题目很简单，但是真上手去做，还是要想一想。由于只有三个杯子，我们可以先对这三个杯子的容积进行排序。我们把排序之后的三个杯子从小到大分别叫做A、B、C。

首先观察几个例子就可以发现，当这三个杯子大小关系不同时，我们采取的策略也是不同的。比如如果C容积很大，要大于A+B的话，那么最佳策略当然是A和B分别和C一起灌水，最后C剩余的部分再单独装。这种情况的答案就是C。

C < A+B时，我们就需要换一种策略。A和B在与C装水的时候，要尽量保证A和B剩余的容积尽可能相同，这样的话，我们就可以在装满C之后，同时装A和B，来节省时间。我们把C装满时装入A和B的水也是C，A和B剩余要装的水量是A+B-C，在我们的操作下，它尽量平均地分配在A和B两个杯子中，所以剩余的时间就是(A+B-C)/2。这里要注意，A+B-C的奇偶性，如果是奇数，那么答案还需要再加上1。

代码如下：

class Solution {
public:
    int fillCups(vector<int>& am) {
        sort(am.begin(), am.end());
        int ret = 0;
        if (am[0] + am[1] <= am[2]) {
            return am[2];
        }
        return (am[0] + am[1] - am[2] + 1) / 2 + am[2];
    }
};

无限集中的最小数字

现有一个包含所有正整数的集合 [1, 2, 3, 4, 5, ...] 。

实现 SmallestInfiniteSet 类：

• SmallestInfiniteSet() 初始化 SmallestInfiniteSet 对象以包含 所有 正整数。
• int popSmallest() 移除 并返回该无限集中的最小整数。
• void addBack(int num) 如果正整数 num 不 存在于无限集中，则将一个 num 添加 到该无限集中。

题解

这题的范围很小，即使是O(n2)O(n^2)O(n2)的时间复杂度或空间复杂度都没有关系。并且最大的数据范围只有1000，我这里直接用了一个长度为1000的数组来标记一个数字有没有被删除掉，用一个标记l来记录当前存在的最小元素。

在popSmallest操作的时候，通过循环寻找下一个没有被删除的元素。在addBack的时候，修改对应的标记即可。

class SmallestInfiniteSet {
public:
    
    vector<int> nums;
    int l;
    
    SmallestInfiniteSet() {
        nums = vector<int>(1005, 1);
        l = 1;
    }
    
    int popSmallest() {
        int ret = l;
        nums[l] = 0;
        for (int i = l+1; i < 1001; i++) {
            if (nums[i] == 1) {
                l = i;
                break;
            }
        }
        return ret;
    }
    
    void addBack(int num) {
        if (num < l) l = num;
        nums[num] = 1;
    }
};

/**
 * Your SmallestInfiniteSet object will be instantiated and called as such:
 * SmallestInfiniteSet* obj = new SmallestInfiniteSet();
 * int param_1 = obj->popSmallest();
 * obj->addBack(num);
 */

移动片段得到字符串

给你两个字符串 start 和 target ，长度均为 n 。每个字符串 仅 由字符 'L'、'R' 和 '_' 组成，其中：

• 字符 'L' 和 'R' 表示片段，其中片段 'L' 只有在其左侧直接存在一个 空位 时才能向 左 移动，而片段 'R' 只有在其右侧直接存在一个 空位 时才能向 右 移动。
• 字符 '_' 表示可以被 任意 'L' 或 'R' 片段占据的空位。

如果在移动字符串 start 中的片段任意次之后可以得到字符串 target ，返回 true ；否则，返回 false 。

题解

这一题乍一看题是有点难的，因为涉及到字符串的处理，而且字母还可以移动，叠加在一起看起来有些棘手。

但是我们稍微分析一下会发现题目中的限制其实还是挺明显的，因为L只能往左，R只能往右，字母之间不能交叉。所以我们只需要判断在L只能往左，R只能往右的前提下，start能否变成target即可。

具体怎么判断呢？我们遍历start和target中的每一个字母进行比对。首先要这两个字符相等，其次在L只能往左，R只能往右的前提下，判断start中的字符能否移动到target中同样的位置。比如同样的L，如果start中的L在target中的左侧，那么就不能成立，因为L不能往右移动。R也是同理。

这里，我使用了两个pair<int, char>的vector来分别记录了start和target中的每一个字符以及它的位置。接着再来分别判断，每一个字符是否相同，并且能否通过移动到达同样的位置。

class Solution {
public:
    bool canChange(string st, string tt) {
        typedef pair<int, char> pic;
        vector<pic> vs, vt;
        
        int n = st.length();
        for (int i = 0; i < n; i++) {
            if (st[i] == 'L' || st[i] == 'R') {
                vs.push_back(make_pair(i, st[i]));
            }
            if (tt[i] == 'L' || tt[i] == 'R') {
                vt.push_back(make_pair(i, tt[i]));
            }
        }
        
        int m = vs.size();
        if (vs.size() != vt.size()) return false;
        for (int i = 0; i < m; i++) {
            if (vs[i].second != vt[i].second) {
                return false;
            }

            if (vs[i].second == 'L') {
                if (vs[i].first >= vt[i].first)
                    vs[i].first = vt[i].first;
                else
                    return false;
            }
            if (vs[i].second == 'R') {
                if (vs[i].first <= vt[i].first)
                    vs[i].first = vt[i].first;
                else
                    return false;
            }
        }
        return true;
    }
};

统计理想数组的数目

给你两个整数 n 和 maxValue ，用于描述一个 理想数组 。

对于下标从 0 开始、长度为 n 的整数数组 arr ，如果满足以下条件，则认为该数组是一个 理想数组 ：

• 每个 arr[i] 都是从 1 到 maxValue 范围内的一个值，其中 0 <= i < n 。
• 每个 arr[i] 都可以被 arr[i - 1] 整除，其中 0 < i < n 。

返回长度为 n 的 不同 理想数组的数目。由于答案可能很大，返回对 109 + 7 取余的结果。

题解

这题简直了，难度有点太大了，我赛后推导了半天，感觉不是很适合比赛。但即使这样，仍然有很多大佬在赛中做出了这题，怎么说呢，给跪一个吧……

我们很容易找到状态转移，如果我们以dp[i][j]表示以i开头长度为j的数组的数量。那么对于dp[i][j+1]来说，它等于[1, maxValue]这个区间当中所有能被i整除的k对应的dp[k][j]的和。

这个结论是怎么得到的呢？很简单，当k能被i整除时，意味着我们可以在数字k之前放入一个i，并且得到的数组依然是完美的。对于所有能够被i整除的k我们都能这么干。

这个状态转移方程相对来说还比较容易发现，但是发现了它并没有卵用。因为在本题当中状态数和转移数的数量都非常大，这么搞铁定超时。

那还有什么其他的办法吗？

我们可以反其道行之，思考以i结尾的情况。对于以i结尾的完美数组来说，i之前的可以放的数也是确定的，它们都必须是i的因子。我们可以通过分解质因数的方式找出i所有的因子，并且可以保证i的因子数量不会超过log⁡i\log ilogi 这个范围。

这里面有一个问题，比如说当i是6时，2和3都是它的因子，但2不能和3同时出现在同一个数组当中。因为2不是3的因子。这就使得我们需要对这些因子进行分类，怎么分类呢，按照质因数分类，分别计算完美数组的数量。最后再把这些所有的情况乘起来。

假设，现在我们知道了数字i某一个质因数ppp的幂是k，我们怎么求它对应的完美数组的数量呢？

我们可以先试着写出数列：

其中an=pma_n = p^man​=pm，因为我们要保证数组的最后一个数是i。因为这个数列当中都是ppp的幂，我们可以进一步简化一下，把底数去掉，只看指数。并且这个数列还存在大小关系：

我们怎么求满足条件的数列的总数呢？

这需要经过一系列的变形，我们令a0=0a_0 = 0a0​=0，接着，我们将数列中的元素两两作差之后再求和，可以得到：

我们令b1=a1−a0+1,b2=a2−a1+1,⋯bn=an−an−1+1b_1 = a_1 - a_0+1, b_2 = a_2 - a_1+1, \cdots b_n = a_n - a_{n-1}+1b1​=a1​−a0​+1,b2​=a2​−a1​+1,⋯bn​=an​−an−1​+1，于是我们得到了一个全新的数列bbb,那么∑i=1nbi=n+k\sum_{i=1}^nb_i = n+k∑i=1n​bi​=n+k

由于aaa数列不递减，所以bi∈[1,k+1]b_i \in[1, k+1]bi​∈[1,k+1]，bbb数列的数量就是对应的aaa数列的数量。bbb数列怎么求呢？我们可以转化成盒模型求解，bbb数列的数量求解等价于这个问题：我们当前有nnn个盒子，有n+kn+kn+k个球要放入盒中，要保证每个盒子里至少有一个球，一共有多少种？

求这个问题很简单，我们可以把这n+kn+kn+k个球排成一排，一共有n+k−1n+k-1n+k−1个间隔。我们从中任选n−1n-1n−1个间隔，可以将球分成nnn堆。并且每一堆球的数量至少是一个，且总和刚好等于n+kn+kn+k。我们从n+k−1n+k-1n+k−1个间隔当中任选n−1n-1n−1个，一共有Cn+k−1n−1C_{n+k-1}^{n-1}Cn+k−1n−1​种可能。

在本题当中由于nnn很大，求解Cn+k−1n−1C_{n+k-1}^{n-1}Cn+k−1n−1​可能会超时，我们可以将其转化成Cn+k−1kC_{n+k-1}^kCn+k−1k​来求解。kkk是质因数的幂，由于maxValuemaxValuemaxValue不会超过10000，可以保证kkk不会超过16。

另外，由于我们要计算组合数，还需要取模，由于组合公式当中存在除法。在有除法的取模运算当中需要计算逆元。或者我们可以使用组合Cnk=Cn−1k+Cn−1k−1C_n^k = C_{n-1}^k + C_{n-1}^{k-1}Cnk​=Cn−1k​+Cn−1k−1​的性质来计算，可以规避掉需要算逆元的问题。

在分解质因数的时候我用到了筛法，这不是必须的，因为本题数据范围不大。

完整代码如下：

class Solution {
public:
    
  	// 筛法求质数
    void get_prime(vector<int> &prime, int m) {
        vector<bool> p(m+1, 1);
        for (int i = 2; i <= m; i++) {
            if (p[i]) prime.push_back(i);
            for (int j = i + i; j <= m; j += i) p[j] = false;
        }
    }
    
  	// 分解质因数
    vector<int> factorial(vector<int> &prime, int n) {
        vector<int> ret;
        for (auto p: prime) {
            int cnt = 0;
            while (n % p == 0) {
                n /= p;
                cnt ++;
            }
            if (cnt > 0) ret.push_back(cnt);
        }
        return ret;
    }
    
    int idealArrays(int n, int m) {
        long long Mod = 1e9 + 7;
        
        vector<int> prime;
        get_prime(prime, m);
        
        vector<vector<long long>> cmb(n+20, vector<long long>(20, 0));
        
      	// 处理组合数
        cmb[1][0] = cmb[1][1] = 1;
        for (int i = 2; i < n+20; i++) {
            cmb[i][0] = 1;
            for (int j = 1; j < 16 && j <= i; j++) {
                cmb[i][j] = (cmb[i-1][j] + cmb[i-1][j-1]) % Mod;
            }
        }
        
        long long ret = 1;
        
        for (int i = 2; i <= m; i++) {
            long long cur = 1;
            
            vector<int> fac = factorial(prime, i);
            for (auto x: fac) {
                cur *= cmb[n+x-1][x];
                cur %= Mod;
            }
            
            ret = (ret + cur) % Mod;
        }
        
        return ret;
    }
};

最后一题代码量并不算大，但是难度不小。思路不是非常清晰，需要弯好几个弯不说，在求解的过程当中还会遇到很多阻碍需要解决，进一步增加了难度。

做这样的难题虽然会掉头发，但是也的确学到很多，很锻炼人。我也很久没有在LeetCode当中做过这样的难题了，真的很酸，也很爽。尤其是最后做出来的时候，成就感还是非常强烈的。

关于这次的周赛就先聊到这里，感谢大家的阅读。