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

TechFlow-承志

发布于 2022-09-21 10:41:12

3150

发布于 2022-09-21 10:41:12

文章被收录于专栏：TechFlowTechFlow

作者 | 梁唐

出品 | 公众号：Coder梁（ID：Coder_LT）

大家好，我是梁唐。

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

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

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

image-20220711110438121

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

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

现有一台饮水机，可以制备冷水、温水和热水。每秒钟，可以装满 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(n^2)

的时间复杂度或空间复杂度都没有关系。并且最大的数据范围只有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

这个范围。

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

假设，现在我们知道了数字i某一个质因数

的幂是k，我们怎么求它对应的完美数组的数量呢？

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

a_1, a_2, \cdots, a_n

其中

a_n = p^m

，因为我们要保证数组的最后一个数是i。因为这个数列当中都是

的幂，我们可以进一步简化一下，把底数去掉，只看指数。并且这个数列还存在大小关系：

0 \le a_1 \le a_2 \le \cdots \le a_n = k

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

这需要经过一系列的变形，我们令

a_0 = 0

，接着，我们将数列中的元素两两作差之后再求和，可以得到：

(a_1 - a_0) + (a_2 - a_1) + (a_3 - a_2) + \cdots + (a_n - a_{n-1}) = a_n - a_0 = a_n = k

我们令

b_1 = a_1 - a_0+1, b_2 = a_2 - a_1+1, \cdots b_n = a_n - a_{n-1}+1

，于是我们得到了一个全新的数列

,那么

\sum_{i=1}^nb_i = n+k

由于

数列不递减，所以

b_i \in[1, k+1]

，

数列的数量就是对应的

数列的数量。

数列怎么求呢？我们可以转化成盒模型求解，

数列的数量求解等价于这个问题：我们当前有

个盒子，有

n+k

个球要放入盒中，要保证每个盒子里至少有一个球，一共有多少种？

求这个问题很简单，我们可以把这

n+k

个球排成一排，一共有

n+k-1

个间隔。我们从中任选

n-1

个间隔，可以将球分成

堆。并且每一堆球的数量至少是一个，且总和刚好等于

n+k

。我们从

n+k-1

个间隔当中任选

n-1

个，一共有

C_{n+k-1}^{n-1}

种可能。

在本题当中由于

很大，求解

C_{n+k-1}^{n-1}

可能会超时，我们可以将其转化成

C_{n+k-1}^k

来求解。

是质因数的幂，由于

maxValue

不会超过10000，可以保证

不会超过16。

另外，由于我们要计算组合数，还需要取模，由于组合公式当中存在除法。在有除法的取模运算当中需要计算逆元。或者我们可以使用组合

C_n^k = C_{n-1}^k + C_{n-1}^{k-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当中做过这样的难题了，真的很酸，也很爽。尤其是最后做出来的时候，成就感还是非常强烈的。

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

喜欢本文的话不要忘记三连~

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2022-07-11，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自 Coder梁微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度