leetcode 周赛 493，排名96

零、背景

这次比赛最后一题是并查集，不难，第三题是枚举倒是稍微复杂一些，花费了至少半个小时去调试。

本场题型概览如下。
A 题：贪心。
B 题：分段统计。
C 题：前缀和+枚举。
D 题：并查集。

最终排名：96。
代码仓库：详见 https://github.com/tiankonguse/leetcode-solutions。

一、统计范围内的逗号

题意：给一个整数 n，问 [1,n] 内的数字都进行标准化，需要多少个逗号。
标准化定义：每三位数字加一个逗号。
数据范围：10^5

思路：贪心
由于是每三位数字加一个逗号，最大值是五位数，所以每个数字最多需要一个逗号。
具体来说，小于 1000 的数字不需要逗号，大于等于 1000 的数字需要一个逗号。
所以，只需要统计大于等于 1000 的数字数量即可。

二、统计范围内的逗号 II

题意：与第一道题类似，数据范围增大到 10^15。

思路：分段统计。
根据第一题找到的规律，可以扩展到所有数据范围：

0 个逗号：[0,10^3)
1 个逗号：[10^3,10^6)
2 个逗号：[10^6,10^9)
3 个逗号：[10^9,10^12)
4 个逗号：[10^12,10^15)
5 个逗号：[10^15,10^18)

故可以分段统计每个区间内的数字数量，然后计算出需要的逗号数量。

三、替换最多一个元素后的最长等差子数组

题意：给一个数组，问至多替换一个元素后，最长等差子数组的长度。

思路：分类讨论+前缀和+枚举

情况一，不修改。
整个数组都是等差数列，直接返回数组长度。

情况二，修改端点。
对于最长的等差数列，随便选择一端，肯定可以替换使得等差数列的长度加一。

情况三，修改中间。
修改中间时，会影响两个差值，只有两个差值相等时才可能得到更长的等差数列。
故，修改元素旁边的两个元素的差值需要是偶数，中间这个值修改为平均数。

修改的值确定了，需要判断修改后的差值与前缀和后缀等差数列是否相等，分三种情况。

情况一，与前缀的等差数列相等，长度加2。
情况二，与后缀的等差数列相等，长度加2。
情况三，与前缀和后缀的等差数列都相等，长度加1。

对于每个点前缀与后缀的等差数列长度，可以预处理得到。
复杂度：O(n)

四、添加一个点后可激活的最大点数

题意：给n个互不相同的二维坐标。
如果两个坐标的 x 坐标或 y 坐标相等，则这两个坐标可以连接。
现在可以任意的添加一个点，问添加这个点后，可以连接的最大的坐标的个数。

思路：并查集

显然，这个是一个图论问题，求最大连通子图大小与次大连通子图大小。

先预处理。每个 x 坐标和 y 坐标，随便记录一个点，当做基准点。
然后对于每个点，与 x 坐标的基准点连接，与 y 坐标的基准点连接。
这样，并查集里就得到了一个图。

然后遍历并查集，统计每个连通子图的大小，存起来。
最后排序，得到最大连通子图的大小和次大连通子图的大小。

特殊情况：如果所有点都连接了，那么最大连通子图的大小就是 n。

五、最后

这次比赛其实不难，但是第三题需要分情况讨论，在加一减一上，容易出错。

《完》。

-EOF-

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