leetcode conttest 301
周赛的质量终于又好起来了，最后一题难度果真上去了。
6112. 装满杯子需要的最短总时长
题目
现有一台饮水机，可以制备冷水、温水和热水。每秒钟，可以装满 2 杯 不同 类型的水或者 1 杯任意类型的水。
给你一个下标从 0 开始、长度为 3 的整数数组 amount ，其中 amount[0]、amount[1] 和 amount[2] 分别表示需要装满冷水、温水和热水的杯子数量。返回装满所有杯子所需的 最少 秒数。
示例 1：
输入：amount = [1,4,2] |
示例 2：
输入：amount = [5,4,4] |
示例 3：
输入：amount = [5,0,0] |
提示：
amount.length == 30 <= amount[i] <= 100
地址
https://leetcode.cn/problems/evaluate-boolean-binary-tree
题意
数学问题 + 贪心匹配
思路
- 假设满足 $a \le b \le c$ 条件，分以下两种情况讨论:
- $a + b \le c$, 此时需要的时间为 $c$ 秒；
- $a + b > c$，次时需要的时间为 $\lceil \frac{a + b - c}{2}\rceil + c$. 设 $t = a + b -c$，$x = \lfloor \frac{t}{2}\rfloor$，此时满足我们知道一定满足 $a >= x$, 否则就不会满足 $b \le c$ 这个条件了，
- 此时如果 $t$ 为偶数，我们令 $a = \frac{t}{2} + a - \frac{t}{2}, b = \frac{t}{2} + b - \frac{t}{2}$, 此时需要的时间即为 $c + \frac{t}{2}$。
- 此时如果 $t$ 为奇数，我们令 $a = x - 1 + (a - x + 1), b = x + b - x$,此时需要的时间即为 $c + x$。
- 复杂度分析：
- 时间复杂度：$O(1)$。
- 空间复杂度：$O(1)$。
代码
class Solution { |
6113. 无限集中的最小数字
题目
现有一个包含所有正整数的集合 [1, 2, 3, 4, 5, ...] 。
实现 SmallestInfiniteSet 类：
SmallestInfiniteSet()初始化SmallestInfiniteSet对象以包含 所有 正整数。int popSmallest()移除 并返回该无限集中的最小整数。void addBack(int num)如果正整数num不 存在于无限集中，则将一个num添加 到该无限集中。
示例：
输入 |
提示：
1 <= num <= 1000- 最多调用
popSmallest和addBack方法 共计1000次
地址
https://leetcode.cn/problems/smallest-number-in-infinite-set
题意
设计问题
思路
- 比较简单的问题，对所有去掉的数用哈希表记录下。
popSmallest: 我们从最小的 $1$ 开始增加，直到其不在哈希表存在记录。addBack：我们将 $num$ 从哈希表中删除即可。
- 复杂度分析：
- 时间复杂度：
popSmallest函数的时间复杂度为 $O(n)$，addBack函数的时间复杂度为 $O(1)$。$n$ 表示函数调用的次数。 - 空间复杂度：$O(n)$。
代码
class SmallestInfiniteSet { |
6114. 移动片段得到字符串
题目
给你两个字符串 start 和 target ，长度均为n 。每个字符串 仅 由字符 'L'、'R' 和 '_' 组成，其中：
字符 'L' 和 'R' 表示片段，其中片段 ‘L’ 只有在其左侧直接存在一个 空位 时才能向 左 移动，而片段 ‘R’ 只有在其右侧直接存在一个 空位 时才能向 右 移动。
字符 ‘_’ 表示可以被 任意 ‘L’ 或 ‘R’ 片段占据的空位。
如果在移动字符串 start 中的片段任意次之后可以得到字符串 target ，返回 true ；否则，返回 false 。
示例 1：
输入：start = "_L__R__R_", target = "L______RR" |
示例 2：
输入：start = "R_L_", target = "__LR" |
示例 3：
输入：start = "_R", target = "R_" |
提示：
n == start.length == target.length1 <= n <= 105start和target由字符'L'、'R'和'_'组成
地址
https://leetcode.cn/problems/move-pieces-to-obtain-a-string
题意
模拟
思路
- 感觉就是直接模拟，我们依次记录 $start, target$ 中所有出现出现的
L,R以及其位置，字符即为字符串 $s_1,s_2$, 索引数组记录为 $p_1,p_2$, 二者比较如下：
- 如果目标字符串的长度不相等，则直接返回
false; - 对于第 $i$ 个字符，如果不满足 $s_1[i] = s_2[i]$ 则直接返回错误；
- 对于第 $i$ 个字符:
- 如果 $s_1[i] = \texttt{‘L’}$, 此时字符只能向左移动，如果不能满足 $p_1[i] \ge p_2[i]$, 则应该返回错误；
- 如果 $s_1[i] = \texttt{‘R’}$, 此时字符只能向右移动，如果不能满足 $p_1[i] \le p_2[i]$, 则应该返回错误；
- 复杂度分析：
- 时间复杂度：$O(n)$, $n$ 表示给定的字符串的长度。
- 空间复杂度：$O(n)$，$n$ 表示给定的字符串的长度。
代码
class Solution { |
6115. 统计理想数组的数目
题目
给你两个整数 n 和 maxValue ，用于描述一个 理想数组 。
对于下标从 0 开始、长度为 n 的整数数组 arr ，如果满足以下条件，则认为该数组是一个 理想数组 ：
- 每个
arr[i]都是从1到maxValue范围内的一个值，其中0 <= i < n。 - 每个
arr[i]都可以被arr[i - 1]整除，其中0 < i < n。
返回长度为n的 不同 理想数组的数目。由于答案可能很大，返回对109 + 7取余的结果。
示例 1：
输入：n = 2, maxValue = 5 |
示例 2：
输入：n = 5, maxValue = 3 |
提示：
2 <= n <= 1041 <= maxValue <= 104
地址
https://leetcode.cn/problems/count-the-number-of-ideal-arrays
题意
动态规划 + 组合数学
思路
- 难得见到质量非常高的数学题目，比赛的时候没有做出来。虽然题目挺难，加一些数学的理论，但是还是感觉这类题目有意思，有思考的深度。
解法1：参考解法：排列组合。
由于题目中满足 $arr[i]$ 能够被 $arr[i-1]$ 整除，假设序列为 $[a_0,a_1,a_2, …, a_{n-1}]$，假设相邻的两个元素进行相除可以得到如下序列 $d = [a_0, \frac{a_2}{a_1},\frac{a_3}{a_2}, \cdots \frac{a_i}{a_{i-1}}, \cdots \frac{a_{n-1}}{a_{n-2}}]$，其中令 $d_{i} = \frac{a_i}{a_{i-1}}$，我们可以知道如下递推关系 $a_{i} = \prod \limits_{j=0}^{i} d_j$，因此我们只需要求出数组 $d$ 就可以求出数组 $arr$，如果我们求出数组 $d$ 的数目。我们设 $f[i]$ 表示数组中的最后一个元素 $arr[n-1]$ 的数组的数组，此时我们知道总共的不同的数组的数组为 $tot = \sum \limits_{i=1}^{maxValue} f[i]$。对于数组中最最后一个元素为 $i$，设 $i$ 的质因子为 $p_0,p_1, …, p_{m-1}$ 则我们知道 $i = p_0^{c_0}p_1^{c_1}p_{m-1}^{c_{m-1}}$，跟局之前的推论我们可以知道 $i = p_0^{c_0}p_1^{c_1}p_{m-1}^{c_{m-1}} = \prod \limits_{j=0}^{n-1} d_j$，此时我们只需要将 $C = \sum \limits_{j = 0}^{m-1}c_j$ 这几个因子放入到 $n$ 个位置中，其中每个位置可以重复放多个元素，剩余未放置元素的位置填入 $1$ 即可。这就等价于将 $m$ 种不同颜色的球放入到 $n$ 个不同的盒子中的不同放置方法的数量，这个不太好求，应该有类似的公式可以直接求解，但是还不太清楚这个排列组合的公式怎么求。但是我们知道一个经典问题，将 $k$ 个相同的球放入到 $n$ 个不同的盒子中放置方法为 $C_{n+k-1}^{n-1}$，关于组合数学问题的解释可以参考 「3分钟帮你完全理解排列组合中的隔板问题」，这个解释得非常清晰易懂。因此我们就知道了对于 $f[i] = \prod \limits_{j=0}^{m}C_{n + c_j-1}^{n-1}$，这样我们就很容易的求出答案了。关于乘法逆元的证明：四种方法求乘法逆元！四种！中间涉及的细节问题：求组合的经典数学公式与乘法逆元的计算公式如下:
$$
C_{i}^{j} = C_{i-1}^{j} + C_{i-1}^{j-1} \
C_{i}^{j} = \frac{A_{i}^{j}}{j!} = \frac{A!}{(i-j)! \times j!} \
C_{i}^{j} \mod P = \frac{A!}{(i-j)! \times j!} \mod P
= A! \times ((i-j)!)^{-1} \times (j!)^{-1} \mod P \
x \times x^{-1} \mod P \equiv 1 \mod P \
x \times x^{P-2} \mod P \equiv 1 \mod P \
x^{-1} = x^{P-2} \mod P
$$
关于阶乘的逆元的计算:
$$
x^{-1} \times y^{-1} = (x \times y)^{-1}\
(n!)^{-1} \times (n + 1) \times (n + 1)^{-1} \equiv (n!)^{-1} \mod P \
((n+1)!)^{-1} \times (n + 1)\equiv (n!)^{-1} \mod P \
n + 1 \equiv (n+1)! \times (n!)^{-1} \mod P \
(n + 1)^{-1} \equiv ((n+1)!)^{-1} \times n! \mod P
$$复杂度分析：
- 时间复杂度：$m \log \log m$，$m$ 表示 $maxvalue$。
- 空间复杂度：$m \times \log m$，$m$ 表示 $maxvalue$。
解法2：参考解法：线性筛选法。感觉这个解法理解起来太难了。用到了非常多的数学理论知识。
代码
- 解法一:
const int MAX_FACTOR_NUM = 20;
const long long MOD = 1e9 + 7;
class Solution {
public:
int idealArrays(int n, int maxValue) {
int maxn = n + MAX_FACTOR_NUM;
vector<vector<int>> primer(maxValue + 1);
vector<vector<long long>> comb(maxn + 1, vector<long long>(MAX_FACTOR_NUM + 1, 1L));
for (int i = 2; i <= maxValue; i++) {
int x = i;
for (int p = 2; p * p <= x; p++) {
int c = 0;
while (x % p == 0) {
c++;
x /= p;
}
if (c > 0) {
primer[i].emplace_back(c);
}
}
/* x 本身为质数 */
if (x > 1) {
primer[i].emplace_back(1);
}
}
for (int i = 2; i <= maxn; i++) {
for (int j = 1; j < i && j <= MAX_FACTOR_NUM; j++) {
comb[i][j] = (comb[i-1][j] + comb[i-1][j-1]) % MOD;
}
}
long long ans = 0;
for (int i = 1; i <= maxValue; i++) {
long long curr = 1L;
for (auto c : primer[i]) {
curr = (curr * comb[n + c - 1][c]) % MOD;
}
ans = (ans + curr) % MOD;
}
return ans % MOD;
}
};
欢迎关注和打赏，感谢支持！
- 关注我的博客: http://mikemeng.org/
- 关注我的知乎：https://www.zhihu.com/people/da-hua-niu
- 关注我的微信公众号: 公务程序猿
扫描二维码，分享此文章