leetcode 第 373 场算法比赛

零、背景

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

中午趁着天热回来休息的时间，做了一下比赛题，写一下题解。

A: 循环模拟题。
B: 预先统计前缀差，两层循环暴力枚举答案。
C: 分组排序。
D: 预先统计前缀差，分组后聚合相同偏移量，计算答案。

总结：没有较高级的数据结构和算法，只需要普通的算法求解答案。

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

一、循环移位后的矩阵相似检查

题意：给一个矩阵，偶数行循环左移k位，奇数行循环右移k位，问是否能得到原矩阵。

思路：每行按奇偶性判断左移或右移后，对应的位置是否与当前位置相等。
只要有一个不相等，就没答案。

二、统计美丽子字符串 I

题意：给一个字符串，问有多少个子串，元音与辅音字母个数相等，且两个个数的乘积可以整除 k。

算法1：求答案。
定义函数: count(l, r) 为区间内元音与辅音个数
枚举所有子串，求元音与辅音个数，判断是否满足。
复杂度：O(n^2) * count(l, r)

算法2: 求区间内元音与辅音个数。
预处理前缀中元音与辅音的个数，通过两个前缀求差即可。
预处理复杂度: O(n)
count(l, r) 复杂度: O(1)

三、交换得到字典序最小的数组

题意：给一个数组，如果两个数字的差值不大于 Limit，则可以交换。
求无数次交换后，字典序最小的数组。

思路：基本思路是满足要求的数组对连一条边，使用并查集对数组内数字分组。
但是数据范围很大，数字之间的边可能会很多，最坏有O(n^2)个。

优化：对数组排序，只对相邻的数字连边，这样图就转化为链了。

优化2：排序后，分组内的数字已经找到了，为一段连续的数字，所以不需要使用并查集了。

找到分组内的所有数字和下标后，数字从小到大遍历，下标也从小到大遍历，依次赋值即可。

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

四、统计美丽子字符串 II

题意：给一个字符串，问有多少个子串，元音与辅音字母个数相等，且两个个数的乘积可以整除 k。

思路: 与第二题一样，字符串长度变为 10^5， k 比较小，范围为 1000。
所以突破口在 k 上。

分析分组条件
如果 k 是 3，则元音的个数必须是 3 的倍数，辅音的个数必须是 3 的倍数，所以答案的长度必须是 3 的倍数。
如果 k 是 9，则元音的个数和辅音个数都是 3 即可满足要求。

所以，需要对 k 进行质因数分解，求出元音和辅音的最小个数。
算法: 每个质数的幂可以凑齐偶数后再折半，一半给元音个数，一半给辅音个数。

假设起始位置是 0 时，可能得答案字符串为 0,2k,4k,8k,...。
同理，起始位置是 1 时，可能得答案字符串为 1,1+2k,1+4k,1+8k,...。

从上面的答案字符串位置可以看到两个规律。

规律1：起始位置小于 2k时，答案字符串之间没有交集。
规律2: 起始位置大于等于 2k时，答案字符串会与模2k的起始位置有交集，通过前缀之间求差得到。
例如起始位置为0 的答案字符串，都减去2k，即可得到起始位置为2k的答案字符字符串。

因此，我们只需要枚举前 2k 个起始位置，对字符串进行分组，求出所有前缀字符串的元音辅音个数差值。

分组内的，任意两个前缀字符串求差，都满足模 k 等于 0 的条件。
所以，我们只需要分情况，找出分组内，满足元音个数与辅音个数相等的答案。

情况1: 差值为0的前缀字符串都是答案，且任何两个前缀之间求差，也是答案。
情况2: 差值不为0时，任何两个前缀的差值是答案。

统计这两种情况的答案。

上面的逻辑文字说明比较复杂，代码其实很简单，就下面几行。

五、最后

这次比赛题目不难，很适合拿来当做面试题。

《完》

-EOF-

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