leetcode 第 412 场算法比赛

零、背景

这次参加比赛了，但是决策错误，没做第三题就先做最后一题了，结果到比赛结束最后一题也没通过。

A: 最小堆模拟。
B: 暴力判断。
C: 分段+快速幂。
D: 分情况讨论。

排名：无
代码地址： https://github.com/tiankonguse/leetcode-solutions/tree/master/contest/4/412

一、 K 次乘运算后的最终数组 I

题意：给一个数组，每次可以选择最小值乘以 P，问操作 K 次后数组的值。

思路：数据范围不大，维护一个最小堆，模拟即可。

复杂度：O(nk)

二、统计近似相等数对 I

题意：给一个数组，问近似相等的元素对。
近似相等定义：两个元素，选择一个元素，最多执行一次位数交换，使得两个元素相等。

思路：数据量不大，枚举两个元素，判断是否是近似相等。

近似相等分为两种情况：

1）不交换就相等
2）恰好有两位不等，且交换后相等。

复杂度：O(n^2 log(V))

三、K 次乘运算后的最终数组 II

题意：给一个数组，每次可以选择最小值乘以 P，问操作 K 次后数组的值。

思路：与第一题一样，不过 K 会很大，模拟会超时。

分析模拟的过程，一开始最小值乘以 P 后，重新插入最小堆时，是插入在中间的，即堆中原先有比新值更大的元素。
操作若干次，当遇到第一个最小值乘以P 不小于最大值时，后续插入的元素都是始终大于最大值的。

这意味着，每操作一次，最小值就会变成最大值。
那操作 N 次，就是整个数组都乘以 P。
操作 a*N次，就是整个数组都乘以 P^a 次。

由此，可以推导出这道题的算法：分类讨论。

首先判断数组所有元素都乘以 P 若干次，首次大于等于最大值时的累计次数 sum。
复杂度：O(n log(V))

如果累计次数不大于 K，则直接使用第一题的暴力代码计算即可。
如果累计次数大于K，则先暴力计算，使得所有值都首次大于最大值，K用过后也需要进行减一操作。

令A=K/N，B=K%N。
根据上面推到的最小值乘以P是最大值的规律，可以确定整个数组至少要进行 A 轮完整的乘法。
故，所有值都需要乘以 P^A，可以使用快速幂计算。
剩余的 B 次不大于 N，再暴力计算即可。

综合复杂度：O(n log(n))

四、统计近似相等数对 II

题意：给一个数组，问近似相等的元素对。
近似相等定义：两个元素，选择一个元素，最多执行两次位数交换，使得两个元素相等。

思路：与第二题的区别是一次变为两次，另外数据范围变大了。

数据范围是 5000， 很容易想到暴力计算。
复杂度：O(n^2 log(n))
cpp 超时了，各种预处理，优化到 O(n^2) 还是超时了，所以比赛没通过这道题。

赛后一想，还可以枚举元素，判断操作后的值与多少其他元素相等。
由于枚举的时候，两个元素会互相计算对方一次，最终答案需要除以2。

再看看复杂度，远远小于 O(n^2)。
复杂度：n * (C(7,2) + C(7,3) + C(7,4) * 4)

枚举一个元素后分为四种情况。

1）直接相等

假设相等的有 count[v]个，需要排除自己，故答案有 count[v]-1个。

2）2位交换1次

枚举任意两位，需要两位的值不相等，交换后，新值的个数就是答案。

3）3位交换2次

枚举任意三位，需要满足三位任意两位都不等。
分析一下，可以发现三位交换只存在两种情况。

例如对于 123,最终只可以交换出231 和 312。
对于两种情况，分别计算交换后的答案。

4）4位交换2次

枚举任意四位，进行两两匹配。
两两匹配分为三种情况：即第一位分别和其他三位匹配，剩余的两个之间匹配。
同样，匹配的两个元素不能相等，否则等价于2位交换1次的情况。

另外还存在一种特殊情况。
例如0011,匹配的值是1100。
第一个元素与第三或第三个元素匹配，都可以得到1100。
这导致答案多算一次。

对于这种情况进行特殊判断，减去即可。

五、最后

这次比赛最后一题其实出的不好，使用5000*5000的数据来卡复杂度，这会导致有些编程语言可以通过，有些无法通过，从而导致不公平。

如果最后一题把数据范围从 5000 改成 50000 的话，应该就好多了吧。
另外第三题质量也不错，分段讨论，小数据无规律，大数据有规律，很有意思。

《完》

-EOF-

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