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;
}
