第 72 场双周赛
链接↓
第 72 场双周赛
这场手速场，题目质量过低（…
5996.统计数组中相等且可以被整除的数对
给你一个下标从 0 开始长度为 n 的整数数组 nums 和一个整数 k ，请你返回满足 0 <= i < j < n ，nums[i] == nums[j] 且 (i * j) 能被 k 整除的数对 (i, j) 的 数目 。
示例 1：
1
2
3
4
5
6
7
8
| 输入：nums = [3,1,2,2,2,1,3], k = 2
输出：4
解释：
总共有 4 对数符合所有要求：
- nums[0] == nums[6] 且 0 * 6 == 0 ，能被 2 整除。
- nums[2] == nums[3] 且 2 * 3 == 6 ，能被 2 整除。
- nums[2] == nums[4] 且 2 * 4 == 8 ，能被 2 整除。
- nums[3] == nums[4] 且 3 * 4 == 12 ，能被 2 整除。
|
示例 2：
1
2
3
| 输入：nums = [1,2,3,4], k = 1
输出：0
解释：由于数组中没有重复数值，所以没有数对 (i,j) 符合所有要求。
|
提示：
1 <= nums.length <= 1001 <= nums[i], k <= 100
分析：
直接暴力，按题目意思
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
int countPairs(vector<int>& nums, int k) {
int ans=0;
for(int i=0;i<nums.size();i++){
for(int j=i+1;j<nums.size();j++){
if(nums[i]==nums[j]){
if((i*j)%k==0){
ans++;
}
}
}
}
return ans;
}
};
|
5997.找到和为给定整数的三个连续整数
给你一个整数 num ，请你返回三个连续的整数，它们的 和 为 num 。如果 num 无法被表示成三个连续整数的和，请你返回一个 空 数组。
示例 1：
1
2
3
4
| 输入：num = 33
输出：[10,11,12]
解释：33 可以表示为 10 + 11 + 12 = 33 。
10, 11, 12 是 3 个连续整数，所以返回 [10, 11, 12]
|
示例 2：
1
2
3
| 输入：num = 4
输出：[]
解释：没有办法将 4 表示成 3 个连续整数的和。
|
提示：
分析：
按题目意思
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public:
vector<long long> sumOfThree(long long num) {
vector<long long> ans;
if(num%3==0){
ans.push_back(num/3-1);
ans.push_back(num/3);
ans.push_back(num/3+1);
}
return ans;
}
};
|
这也叫Medium难度？
5998.拆分成最多数目的偶整数之和
给你一个整数 finalSum 。请你将它拆分成若干个 互不相同 的偶整数之和，且拆分出来的偶整数数目 最多 。
- 比方说，给你
finalSum = 12 ，那么这些拆分是 符合要求 的（互不相同的偶整数且和为 finalSum）：(2 + 10) ，(2 + 4 + 6) 和 (4 + 8) 。它们中，(2 + 4 + 6) 包含最多数目的整数。注意 finalSum 不能拆分成 (2 + 2 + 4 + 4) ，因为拆分出来的整数必须互不相同。
请你返回一个整数数组，表示将整数拆分成 最多 数目的偶整数数组。如果没有办法将 finalSum 进行拆分，请你返回一个 空 数组。你可以按 任意 顺序返回这些整数。
示例 1：
1
2
3
4
5
| 输入：finalSum = 12
输出：[2,4,6]
解释：以下是一些符合要求的拆分：(2 + 10)，(2 + 4 + 6) 和 (4 + 8) 。
(2 + 4 + 6) 为最多数目的整数，数目为 3 ，所以我们返回 [2,4,6] 。
[2,6,4] ，[6,2,4] 等等也都是可行的解。
|
示例 2：
1
2
3
4
| 输入：finalSum = 7
输出：[]
解释：没有办法将 finalSum 进行拆分。
所以返回空数组。
|
示例 3：
1
2
3
4
5
| 输入：finalSum = 28
输出：[6,8,2,12]
解释：以下是一些符合要求的拆分：(2 + 26)，(6 + 8 + 2 + 12) 和 (4 + 24) 。
(6 + 8 + 2 + 12) 有最多数目的整数，数目为 4 ，所以我们返回 [6,8,2,12] 。
[10,2,4,12] ，[6,2,4,16] 等等也都是可行的解。
|
提示：
小彩蛋：
有意思的是我报错的时候，样例给出了2，然后我返回了[2,0],直接给我报错了。
在中文题目里第一行最后一句偶整数数目 最多 。
在英文描述里positive even integers.
真有他的.jpg
分析：
首先考虑是否能mod2
不能的话直接返回空数组
记录一个最小的 正偶数 ，用结果值去作差，每完成一次放入就到下一个正偶数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution {
public:
vector<long long> maximumEvenSplit(long long f) {
vector<long long> ans;
int a=2;
if(f%2!=0){
return ans;
}
if(f==4){
ans.push_back(f);
return ans;
}
else{
while(f){
ans.push_back(a);
f-=a;
if(f==0){
break;
}
if((f/2)-2<=a){
ans.push_back(f);
break;
}
a+=2;
}
}
return ans;
}
};
|
5999.统计数组中好三元组数目
给你两个下标从 0 开始且长度为 n 的整数数组 nums1 和 nums2 ，两者都是 [0, 1, ..., n - 1] 的 排列 。
好三元组 指的是 3 个 互不相同 的值，且它们在数组 nums1 和 nums2 中出现顺序保持一致。换句话说，如果我们将 pos1v 记为值 v 在 nums1 中出现的位置，pos2v 为值 v 在 nums2 中的位置，那么一个好三元组定义为 0 <= x, y, z <= n - 1 ，且 pos1x < pos1y < pos1z 和 pos2x < pos2y < pos2z 都成立的 (x, y, z) 。
请你返回好三元组的 总数目 。
示例 1：
1
2
3
4
5
| 输入：nums1 = [2,0,1,3], nums2 = [0,1,2,3]
输出：1
解释：
总共有 4 个三元组 (x,y,z) 满足 pos1x < pos1y < pos1z ，分别是 (2,0,1) ，(2,0,3) ，(2,1,3) 和 (0,1,3) 。
这些三元组中，只有 (0,1,3) 满足 pos2x < pos2y < pos2z 。所以只有 1 个好三元组。
|
示例 2：
1
2
3
| 输入：nums1 = [4,0,1,3,2], nums2 = [4,1,0,2,3]
输出：4
解释：总共有 4 个好三元组 (4,0,3) ，(4,0,2) ，(4,1,3) 和 (4,1,2) 。
|
提示：
n == nums1.length == nums2.length3 <= n <= 1050 <= nums1[i], nums2[i] <= n - 1nums1 和 nums2 是 [0, 1, ..., n - 1] 的排列。
分析：
首先记录每一个nums2的位置
然后用值去替换nums1和nums2中数字
例如：
nums1第i个位置是v，那么我们把所有v都替换成i+1 (1~N)
借助树状数组统计
其次就是
找x
我们统计值小于nums2[i]且在第二个数组中出现在nums2[i]之前的数字有几个
//getSum(nums2[i]-1)个
找z
在找x的操作逆序遍历即可
//(nums1.size()-1-i-getSum(nums2[i]))个
最后进行一个求和即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| #define LL long long
const int MAX=1e5+55;
int revp[MAX];
LL dans[MAX];
LL sum[MAX];
int lowbit(int x){
return x&(-x);
}
void addSum(int x){
for(int i=x;i<MAX;i+=lowbit(i)) sum[i]+=1;
}
int getSum(int x){
int ret=0;
for(int i=x;i;i-=lowbit(i)) ret+=sum[i];
return ret;
}
class Solution {
public:
long long goodTriplets(vector<int>& nums1, vector<int>& nums2) {
for(int i=0;i<nums1.size();i++) revp[nums2[i]]=i;
for(int i=0;i<nums1.size();i++){
int v=nums1[i];
nums2[revp[v]]=i+1;
}
for(int i=0;i<=nums1.size();i++){
sum[i]=0;
dans[i]=1;
}
for(int i=0;i<nums1.size();i++){
dans[i]=dans[i]*getSum(nums2[i]-1);
addSum(nums2[i]);
}
for(int i=0;i<=nums1.size();i++) sum[i]=0;
for(int i=nums1.size()-1;i>=0;i--){
dans[i]*=(nums1.size()-1-i-getSum(nums2[i]));
addSum(nums2[i]);
}
LL ans=0;
for(int i=0;i<nums1.size();i++) ans=ans+dans[i];
return ans;
}
};
|