LeetCode周赛330，开工第一天从刷LeetCode开始
LeetCode周赛330，开工第一天从刷LeetCode开始
作者 | 梁唐
出品 | 公众号：Coder梁（ID：Coder_LT）
大家好，我是梁唐。
非常惭愧，LeetCode系列过年期间偷懒停了几期。逼迫了自己一把，恢复正常更新。
昨天的这一场是LeetCode周赛第330场，是力扣官方举办的贺岁场。整场赛题的质量还不错，难度梯度做得很好。
大年初七是工作日，估计很多大佬忙于工作没能参加。但评论区依然欢乐，甚至有菊苣摸鱼参赛，不得不令人佩服。
统计桌面上的不同数字
给你一个正整数 n ，开始时，它放在桌面上。在 109 天内，每天都要执行下述步骤：
- 对于出现在桌面上的每个数字
x，找出符合1 <= i <= n且满足x % i == 1的所有数字i。 - 然后，将这些数字放在桌面上。
返回在
天之后，出现在桌面上的 不同 整数的数目。
注意：
- 一旦数字放在桌面上，则会一直保留直到结束。
%表示取余运算。例如，14 % 3等于2。
题解
题目问
天之后的结果，看起来很唬人。这么大的规模我们都没办法枚举，但稍微分析一下就会发现，对于每一个数
来说，它能产生的数字一定比它本身要小，并且不会有负数。所以对于确定的输入
来说，能够衍生的范围是固定的就是[0, n]。
既然是一个固定的范围， 那么必然会收敛，不会无限繁衍下去。那么我们只需要使用一重while循环，当不再产生新元素的时候停止即可。
class Solution {
public:
int distinctIntegers(int n) {
// 记录桌面上的数字
set<int> vt;
vt.insert(n);
bool flag = true;
while (flag) {
flag = false;
set<int> cur = vt;
for (auto x: vt) {
// 枚举可能产生的新数
for (int i = 1; i < x; i++) {
if (x % i == 1) cur.insert(i);
}
}
if (cur.size() > vt.size()) {
flag = true;
vt = cur;
}
}
return vt.size();
}
};
猴子碰撞的方法数
现在有一个正凸多边形，其上共有 n 个顶点。顶点按顺时针方向从 0 到 n - 1 依次编号。每个顶点上 正好有一只猴子 。下图中是一个 6 个顶点的凸多边形。
每个猴子同时移动到相邻的顶点。顶点 i 的相邻顶点可以是：
- 顺时针方向的顶点
(i + 1) % n，或 - 逆时针方向的顶点
(i - 1 + n) % n。
如果移动后至少有两个猴子位于同一顶点，则会发生 碰撞 。
返回猴子至少发生 一次碰撞 的移动方法数。由于答案可能非常大，请返回对 109+7 取余后的结果。
注意，每只猴子只能移动一次。
题解
这题同样看起来很难，不仅数据范围很大，而且情况看起来好像也很复杂。
但实际上这题是一个障眼法，可以考虑不会出现碰撞的情况，容易发现只有所有猴子都往一个方向移动才不会出现碰撞。每只猴子有两个移动方向，一共有
只猴子，所以最终的结果一共有
种。其中不会出现碰撞的只有两种，本质上这题就是求
。
然而由于
可能非常大，所以需要使用快速幂。快速幂的原理很简单，我们使用一个数组
，其中
。由于每个整数都可以表达成二进制形式，所以我们要求
时，就可以将
转化成二进制。将二进制位为1的对应的
相乘，即可得到答案。
class Solution {
public:
int monkeyMove(int n) {
long long Mod = 1e9 + 7;
long long ret = 1;
vector<long long> vt;
vt.push_back(2);
for (int i = 1; i < 35; i++) {
vt.push_back(vt[i-1] * vt[i-1] % Mod);
}
for (int i = 0; i < 35; i++) {
if (n & (1ll << i)) {
ret = ret * vt[i] % Mod;
}
}
return (((ret - 2) % Mod) + Mod) % Mod;
}
};
将珠子放入背包中
你有 k 个背包。给你一个下标从 0 开始的整数数组 weights ，其中 weights[i] 是第 i 个珠子的重量。同时给你整数 k 。
请你按照如下规则将所有的珠子放进 k 个背包。
- 没有背包是空的。
- 如果第
i个珠子和第j个珠子在同一个背包里，那么下标在i到j之间的所有珠子都必须在这同一个背包中。 - 如果一个背包有下标从
i到j的所有珠子，那么这个背包的价格是weights[i] + weights[j]。
一个珠子分配方案的 分数 是所有 k 个背包的价格之和。
请你返回所有分配方案中，最大分数 与 最小分数 的 差值 为多少。
题解
分析一下题意，会发现本题的核心是将数组分割成连续的几段子数组，对于每一段子数组的值等于首尾两个端点的和。
从整体上来看，每次多切分一个子数组，整体的总和就会增加切分处的两个值。已知我们一共要切分成
段，也就是说我们要切分
次。很容易想到，这里可以使用贪心的思想。我们可以把所有可以拆分处产生的增益进行排序，选择其中最小的
个即能得到最小值，选择其中最大的
个则能得到最大值。
把最小值和最大值相减即可。
class Solution {
public:
long long putMarbles(vector<int>& weights, int k) {
int n = weights.size();
vector<long long> sm;
// 每一个位置都可以拆分，填入数组
for (int i = 0; i < n-1; i++) {
sm.push_back(weights[i] + weights[i+1]);
}
sort(sm.begin(), sm.end());
long long mini = 0, maxi = 0;
for (int i = 0; i < k-1; i++) mini += sm[i];
for (int i = n-k; i < n-1; i++) maxi += sm[i];
return maxi - mini;
}
};
统计上升四元组
给你一个长度为 n 下标从 0 开始的整数数组 nums ，它包含 1 到 n 的所有数字，请你返回上升四元组的数目。
如果一个四元组 (i, j, k, l) 满足以下条件，我们称它是上升的：
0 <= i < j < k < l < n且nums[i] < nums[k] < nums[j] < nums[l]。
题解
这题的trick在于选出来的四元组并不是完全递增的，而是中间两个位置逆序。直接遵照题意来操作会比较棘手，我们可以反其道行之。对于i, j, k, l这四个位置，我们可以求出所有下标小于i，并且数值小于等于nums[k]的数量以及下标大于k，并且数值大于等于nums[j]的数量，两者相乘即是答案。
所以剩下的问题就是怎么求这两个数量呢？这里用到了二维前缀和的思想，又是二维前缀和的问题，已经在周赛遇到过好几次了。其实本质上就是一维前缀和在二维的延伸。我们用f[i][j]记录下标小于等于i，并且元素值小于等于j的数量。g[i][j]表示所有下标大于i，并且元素值大于等于j的数量。
对于nums[i]来说，所有i右侧的位置全部增加1，所以有：for (int i = 1; i <= n; i++) f[i][nums[i-1]] = g[i][nums[i-1]] = 1;
接着，我们只需要分别按行以及案列更新即可，注意，这里为了计算前缀和方便，我们默认把所有下标都+1处理。
for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) f[i][j] += f[i][j-1];
for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) f[i][j] += f[i-1][j];
for (int i = n; i > 0; i--) for (int j = n; j > 0; j--) g[i][j] += g[i][j+1];
for (int i = n; i > 0; i--) for (int j = n; j > 0; j--) g[i][j] += g[i+1][j];
这两个数组有了，答案也就有了。注意本题的时间卡得很紧，f和g数组都只能使用int类型。否则会因为memset操作超时。所以最后返回答案时要将类型再转换回long long。
int f[4010][4010], g[4010][4010];
class Solution {
public:
long long countQuadruplets(vector<int>& nums) {
int n = nums.size();
long long ret = 0;
memset(f, 0, sizeof f);
memset(g, 0, sizeof g);
for (int i = 1; i <= n; i++) f[i][nums[i-1]] = g[i][nums[i-1]] = 1;
for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) f[i][j] += f[i][j-1];
for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) f[i][j] += f[i-1][j];
for (int i = n; i > 0; i--) for (int j = n; j > 0; j--) g[i][j] += g[i][j+1];
for (int i = n; i > 0; i--) for (int j = n; j > 0; j--) g[i][j] += g[i+1][j];
for (int i = 1; i <= n; i++) for (int j = i+1; j <= n; j++) {
if (nums[i-1] > nums[j-1]) {
ret += 1ll * f[i-1][nums[j-1]] * g[j+1][nums[i-1]];
}
}
return ret;
}
};