leetcode 第 316 场算法比赛

零、背景

大家都太厉害了，我昨晚前三题的时候，前百名就做完所有题了。

一、判断两个事件是否存在冲突

题意：给一天内的两个时间区间，问是否有交集。

思路：时间转化为从凌晨的秒数，这样就是两个数字区间是否有交集。

小技巧：先保证第一个区间开始时间是最小的，判断第二个区间的开始时间是否在第一个区间内即可。

二、最大公因数等于 K 的子数组数目

题意：给 n 个整数，问有多少个子数组的最大公约数等于 K。

思路：数据范围不大，枚举所有子数组，利用前缀的答案计算数子数组的最大公约数，判断是否是答案即可。

三、使数组相等的最小开销

题意：给 n 个整数以及每个位置数组操作的代价，问使所有位置数字相等的最小代价。

操作：任意选择一个位置，做加一或减一操作。

思路：对于同一个位置，不可能既有加一操作又有减一操作。
所以假设最终数组的值都是 X，则小于 X 的值肯定是加一操作，大于 X 的肯定是减一操作。

数字值的范围是10^6，我们如果枚举目标值，可以快速求出总代价，就可以做这道题。

假设我们已经求出目标值为 X 的总代价 C ，且小于等于 X 的数字操作一次的代价和是 C1，大于X 数字操作一次的代价和是 C2。
则目标值是 X+1 的代价和可以由前一个计算出来。

转移公式是：C + C1 - C2。

解释：X 左边的都是小于等于 X 的数字，目标变成 X+1时，这些数字都需要加一。
右边同理，都是大于 X 的数字，变成 X+1时，这些数字就可以少减一一次。

计算出 X+1 位置的总代价后，更新新的 C1 和 C2 即可。

四、使数组相似的最少操作次数

题意：给一个数组和目标，现在可以对数组进行操作，问最少操作多少次，可以使得两个数组中每个元素出现的频率相等。

操作：数组中任意选择两个位置，一个位置的值加2，另一个位置的值减2。

思路：

目标是使得两个数组中每个元素出现的频率相等，这句话的含义是两个数组变成集合后，出现的数字完全相等，且每个数字出现的次数也相等。

对于同一个位置的值，要么是加2，要么是减2，不可能同时加与减。
另外，如果一个值大于另外一个值，我们不可能把较大的值减的比较小的值还小。

所以可以直接对两个数组排序，相同位置的值的差值就是需要补齐的，最终除四即可。

注意实现：由于每次操作是加减2，所以需要先按就行对两个数组拆分。

五、最后

这次比赛后两题其实有点意思，尤其是最后一题，需要多思考，然后可以发现可以贪心。

加油，算法人。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code