leetcode 第 211 场算法比赛

零、背景

好久没写文章了，后面找时间把上周的 leetcode 和 昨天的 tpc 比赛报告写下。

今天这比赛总体比较简单，但是我最近不在状态，直到最后几分钟才全部做完题。

比较欣慰的是，这次比赛四道题都是一次通过的。

下面来看看这四道题吧。

一、两个相同字符之间的最长子字符串

题意：给字符串，对于相同的字母，如果有多个，我们可以计算最长的距离差。
求所有字母里面，最大的距离差。
如果不存在距离差（没有相同字母），输出 -1。

思路：统计每个字母的左右边界，取最大距离差即可。

二、执行操作后字典序最小的字符串

题意：对于一个字符串，有两个操作。

1）对所有奇数下标的字符一起向上旋转 a 下。
2）对整个字符一起向右旋转 b 下。

上面两个操作可以任意选择进行无数次，求操作后字典序最小的字符串。

思路：枚举即可。

优先枚举操作2，得到所有左右相对位置固定的字符串。
对于每个固定位置的字符串，按奇偶数拆分为两个子字符串，分别枚举所有旋转次数求字典序最小字符串。

注意事项：默认只能上下旋转奇数字符串。
所有只有左右移动，能够把偶数位置移动到奇数位置时，才能对偶数位置进行上下旋转。

那什么时候偶数位置可以移动到奇数位置呢？
可以证明，移动次数不为偶数时，就可以做到。

三、无矛盾的最佳球队

题意：给一个球队每个球员的年龄和得分，需要组成一个球队，使得球员年龄越大，得分越高。
由于有很多中组合，求总得分最高的球队分数。

思路：动态规划题，即路径问题。

年龄其实就是横坐标，得分就是竖坐标，对应方格的值也是分数（相同的累加）。
这里和普通的路径问题的区别在于部分坐标没有值，按 0 处理。

注意事项：年龄只有一千个，意味着得分最多也有一千个。
而得分数据范围是 100万，需要进行离散化，转化为一千个。

看到这道题，我感觉有点不可思议。
昨天 TPC 比赛的时候有一道类似的题。
不过那道题的数值个数是10万个，二维数组存不下，时间复杂度也是 O(n^2)，然后就没思路了。

回到这道题，能想到路径问题，离散化后两层循环即可搞定。

四、带阈值的图连通性

题意：n 个城市，对于任意两个城市，如果最大公约数大于 K，则认为两个城市直接相连。
q 个询问，问某两个城市是否连通。

思路：按照题意构造出图，然后判断是否连通即可。

由于是 n 的数据范围是 1万，leetcode 也不会超时，暴力枚举就可以构造出图。
由于还需要判断是否连通，直接使用并查集来构造图即可。

acm 的做法是根据素数的倍数进行分组，这样复杂度就大大降低，不会超时了。
我为了快速实现，枚举所有数而不是所有素数，由于是筛法，也不会超时。

五、最后

这次比赛还算简单，但是我也仅仅刚好进入第一百名。
而公司随便进来一个实习生和毕业生好像都可以排到十几名的，新人太厉害了。

还好他们大多数都很忙，不屑于参加 leetcode，不然我能不能进前 500 名都不好说了。

《完》

-EOF-

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