第72场双周赛 蔚来
第一题 5996. 统计数组中相等且可以被整除的数对
题意 & 思路
简单的就是找出满足这些条件
0 <= i < j < n
nums[i] == nums[j]
(i * j)%k==0
的这样一个i,j对的个数。而且该题的数据范围很小所以我们直接双重循环解决。
1 <= nums.length <= 100
1 <= nums[i], k <= 100
代码
class Solution {
public int countPairs(int[] nums, int k) {
int ans = 0;
int n = nums.length;
for(int i = 0; i < n; i++) {
for(int j = i+1; j < n; j++) {
if((i*j) % k == 0 && (nums[i] == nums[j])) {
ans++;
}
}
}
return ans;
}
}
算法时间复杂度O(N^2)
第二题 5997. 找到和为给定整数的三个连续整数
题意
给你一个整数你把它拆分为三个连续整数的和。如果不能拆分就返回空。
思路
我们看下33之类的三个数相加必然包含了33整除3。
我们夹着要求的数字为x
,则有(x/3) + (x/3) - 1 + (x/3) +1 <= x
并且有x >= (x/3) + (x/3) + 1 + (x/3) + 2)
我们只需要求这两个就行了。
代码
class Solution {
public long[] sumOfThree(long num) {
long tmp = num / 3;
long minN = (tmp-1) + tmp + tmp+1;
long maxN = tmp + tmp+1 + tmp+2;
if(minN == num) {
return new long[]{tmp-1, tmp, tmp+1};
} else if(minN == maxN) {
return new long[]{tmp, tmp+1, tmp+2};
} else {
return new long[]{};
}
}
}
算法时间复杂度O(1)
第三题 5998. 拆分成最多数目的偶整数之和
题意
给你一个整数,让你求这个整数能够拆分成多少个偶数,并且这些偶数不能相等。
思路
显然奇数不能被拆分。
我们把这个整数减去一些偶数这些偶数从小到大分别是2,4,6,8,10, ........,这样的,但是并不是所有的都能按顺序拆分我们要判断下他能不能拆分。
比如28,
- 28 - 2 = 26
- 26 - 4 = 22
- 22 - 6 = 16
这里我们判断下16的一半能否被后面一个完整的拆分,也就是判断下(16 - 8) > 8 ?
,我们得到的答案是false,那么我们就不要把16拆分直接使用16即可。
那么我们的答案就是[2,4,6,16]
代码
class Solution {
public List<Long> maximumEvenSplit(long finalSum) {
List<Long> ansList = new ArrayList<>();
if(finalSum % 2 != 0) {
return ansList;
}
long tmp = finalSum;
long cnt = 2;
while(tmp >= cnt) {
if(tmp - cnt > cnt) {
ansList.add(cnt);
tmp -= cnt;
cnt+=2;
} else {
ansList.add(tmp);
break;
}
}
return ansList;
}
}
算法时间复杂度O(√n)
第四题 5999. 统计数组中好三元组数目
还不会做。。。。