作者 | 梁唐
出品 | 公众号: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;
}
};