leetcode 第 376 场算法比赛

零、背景

周末早上我八点之前就出门去练车了，所以就没参加比赛。

下午有《星光大赏》保障活动，所以题目做的比较晚，题解现在才发出来。

A: 离散数学题，循环节替换，找重复数字。
B: 排序
C: 枚举+滑动游标 或者 数学公式直接计算答案。
D: 二分+数学公式。

比赛代码:
https://github.com/tiankonguse/leetcode-solutions/tree/master/contest

一、找出缺失和重复的数字

题意：给一个n*n矩阵，填充1~n^2的数字，有一个数字重复了，问哪个数字重复了，以及哪个数字缺少了。

思路：数据范围很小，方法很多。

1）转化为一维数组排序。
时间复杂度：O(n log(n))
空间复杂度：O(n)

2）hash 储存与判断。
时间复杂度：O(n)
空间复杂度：O(n)

3）循环节置换 时间复杂度：O(n)
空间复杂度：O(1)，无新增空间。

置换原理：
不妨假设题目是一维数组，排序后下标与值就会相等。
对于输入数组，如果位置 i 的值是 v，我们交换 nums[i] 与 nums[v]，则位置 v 的值就是 v 了。
这样不断地交换，除了缺少的数字对应的位置，其他所有位置上都是自己下标对应的值。

二、划分数组并满足最大差限制

题意：给一个数组，问是否可以将数组划分为3个数字一组，且组内的数字之差不大于k。

思路：排序，3 个一组，判断是否合法。

三、使数组成为等数数组的最小代价

题意：给一个数组，每次可以将一个数字加一或者减一。
问是否可以将数组的所有数字修改为相同的回文数字，如果可以，求最小修改次数。

思路1：枚举回文数，计算修改代价，求最小值。

题目要求回文数不大于10^9，则满足要求的回文数个数为 1.1 * 10^5 个。
我们枚举 1 ~ 10^4 - 1, 反转可以组成回文串，可以中间是否重合有两种情况，故回文数为 2 * 10^4 个。
对于 10^4 ~ 10^5 - 1, 组成的回文串只能取中间重合的部分，故个数有 9 * 10^4个。
两个合起来就是 1.1 * 10^5 个。

例如对于数字 123 可以得到下面两个回文数。

中间不重合，得到 6 位回文数 123321。
中间重合，得到 5 位回文数 12321。

计算修改代价：二分找到位置，左边的都需要加，右边的都需要减，通过前缀和优化可以得到答案。

复杂度：O(srqt(MaxV) * log(n))

思路2：枚举回文数，游标快速找到位置。

按顺序枚举回文数，这样就不需要二分查找位置了，直接利用上个回文数的位置快速转移到最新的位置。
计算答案时也没必要使用前缀和，直接维护左右边的个数和前后缀和，游标转移时计算新的答案即可。

复杂度：O(srqt(MaxV))

思路3：直接计算答案。

从小到大枚举答案的时候，可以发现答案只与左右边数字的个数有关系。

ans = min(ans, preAns + leftNum - rightNum);

如果右边数字个数多了，向右边移动时，答案会更优。
如果两边数字相等，移动不影响答案。
如果右边数字个数较少，则向右边移动是，答案会更差。

所以可以推理出答案就是中位数。

直接计算中位数，然后求中位数附近的回文数，求最优答案即可。

复杂度：O(1)

怎么求中位数附近的回文数呢？
与枚举回文数的逻辑相反，根据中位数的奇偶性，得到枚举的数字，然后再枚举这个数字附近区间的数字即可。

四、执行操作使频率分数最大

题意：给一个数组，每次可以将一个数字加一或者减一，问最多修改 k 次，可以得到的最大频率是多少。
最大频率：数字出现的最多次数。

思路1：二分最大频率，判断是否可以在 k 次修改内得到这个频率。

假设区间 [l, r]的数字被修改为相同的数字，如何求最小修改次数呢？
是不是和第三题一模一样？
答案就是修改为中位数时修改代价最小，通过前缀和可以快速计算出答案。

那怎么找到区间 [l,r]呢，枚举所有区间即可。
复杂度：O(n log(n))

思路2：枚举中位数目标数字，二分区间半径，判断 k 次是否可以修改为相同值，从而得到的最大频率。
复杂度：O(n log(n))

PS：由于半径分为左半径和右半径，处理起来稍微复杂点。

五、最后

这次比赛最后两题还是比较有意思的，很经典的题目。

互动问题：你推导出中位数就是答案了吗？

《完》

-EOF-

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