T1:判断两个事件是否存在冲突
思路:判断两个区间是否有交集
public boolean haveConflict(String[] event1, String[] event2) {
// 比较 Unicode 字符, 使用 compareTo 函数
if (event1[1].compareTo(event2[0]) < 0 || event2[1].compareTo(event1[0]) < 0) {
return false;
}
return true;
}
T2:最大公因素等于 K 的子数组数目
思路:暴力枚举
/**
* 求两个数的最大公因数
* @param a
* @param b
* @required a <= b
* @return
*/
public int gcd(int a, int b) {
if (a == 0) {
return b;
}
return gcd(b % a, a);
}
public int subarrayGCD(int[] nums, int k) {
int res = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] % k != 0) {
continue;
}
int temp = nums[i];
for (int j = i; j < nums.length; j++) {
if (nums[j] % k != 0) {
break;
}
temp = gcd(temp, nums[j]);
if (temp % k != 0) {
break;
}
if (temp == k) {
res += 1;
}
}
}
return res;
}
T3:使数组相等的最小开销
思路:中位数贪心,将 cost[i]
转化为 nums[i]
出现的次数,就可以将题目转化为 LeeCode 462: 最小操作次数使数组元素相等II
注意数据大小:
- counts 使用 int 会溢出,之前卡在这里答案一直出错
public long minCost(int[] nums, int[] cost) {
int[][] pairs = new int[nums.length][2];
long counts = 0;
for (int i = 0; i < nums.length; i++) {
pairs[i][0] = nums[i];
pairs[i][1] = cost[i];
counts += cost[i];
}
Arrays.sort(pairs, (o1, o2) -> {
return o1[0] - o2[0];
});
counts /= 2;
int index = 0;
for (; index < pairs.length; index++) {
counts -= pairs[index][1];
if (counts < 0) {
break;
}
}
long res = 0;
for (int i = 0; i < pairs.length; i++) {
if (i == index) {
continue;
}
long diff = Math.abs(pairs[i][0] - pairs[index][0]);
long times = pairs[i][1];
res += diff * times;
}
return res;
}
T4:使数组相似的最少操作
思路:奇偶排序 + 贪心选择
按奇偶分类并排序,让最小的一对,次小的一对,依次类推,最大的组成一对,可以得到 nums
数组变化量的最小值
public long makeSimilar(int[] nums, int[] target) {
Arrays.sort(nums);
Arrays.sort(target);
long res = 0;
// index[0] 表示 target 当前指向的偶元素位置
// index[1] 表示 target 当前指向的奇元素位置
int[] index = new int[2];
for (int num : nums) {
int temp = num % 2;
while (target[index[temp]] % 2 != temp) {
index[num % 2] += 1;
}
res += Math.abs(num - target[index[temp]]);
index[temp] += 1;
}
return res / 4;
}
标签:周赛,pairs,index,int,res,nums,316,long,LeeCode
From: https://www.cnblogs.com/ylyzty/p/16819216.html