leetcode 第 218 场算法比赛

零、背景

这次比赛经历了一次过山车。

前三题 13 分钟敲完了，意气风发的去做最后一题，结果大意了，没闪。

最后一题完全不讲武德，打的我措手不及，想到状态压缩，但是计算复杂度后依旧会超时，完全没想法。

赛后看了题解才发现，闪电五连鞭，接～化～发，才这个知识点我还不知道，学到新知识了，

源代码：
https://github.com/tiankonguse/leetcode-solutions/tree/master/contest/218

一、设计 Goal 解析器

题意：给一些字符串映射规则，求映射后的字符串。

G => G  
() => o  
(al) => al  

思路：由于映射规则不存在递归的问题，直接扫描一遍替换即可。

二、K 和数对的最大数目

题意：给一个数组和 K，每次可以从数组中选两个和为 K 的数字删除，求最多可以删除几次。

思路：对于一个数字，需要找的另外一个数字是固定的。

所以可以实现统计所有数字的个数，然后扫描判断即可。

最优的方法是边扫面边排序，这样一半的数字不需要统计了。

三、连接连续二进制数字

思路：将前 n 个数字的二进制字符串拼接成一个大的二进制，求十进制取模后的答案。

拼接如下，实际没有空格，空格主要是为了使得各数字比较清晰。

1: 1
2: 1 10
3: 1 10 11
4: 1 10 11 100
...

思路：数字范围不大，循环左移或运算计算即可。

四、最小不兼容性

题意：给一个数组和整数 K，求将数组的数字分为 K 个集合。

要求：每个集合里面不能有相同的数字。
规则：每个集合的得分是最大值减去最小值。
目标：所有集合的总得分最小。

思路：数组和值的范围都不超过 16，显然需要进行枚举所有状态，然后通过状态压缩标记这个状态。

但是直接枚举的复杂度最坏情况是 C(16,4)*C(12,4)*C(8,4)。

普通的递归在处理C(12,4)和C(8,4)的时候，依旧需要循环 16 次，从而导致复杂度常数比较高，最终可能超时。

面对这种情况，有三种优化方法。

方法一：接 ~ 枚举子集

状态从(1<<n) - 1 开始枚举。
这样可以通过i = (i - 1) & state 枚举所有的子集，从而不会超时了。

方法二：化 ~ 扫面线状态压缩DP

处理看到这道题，猜想可能是状态压缩DP，但是状态无法储存。
具体就是当前的集合没满的时候，怎么标示已经选择哪些数字。

暴力点就是dp[2^16][2^16]，状态太多了。

如果预先对所有数字排序，那么就可以通过当前集合的最大数字来标示选到哪个数字了。

这样就可以使用dp[2^16][16]个状态储存下来了。

状态转移分两种情况。

1）新的一个集合，与前面的最大数字无依赖，取前面状态的最小值即可。
2）未满的旧即可，选择一个更大的数字，新增得分就是两个数字的差值。

方法三：发 ~ 贪心+暴力搜索

前面我们分析了那么多，实际上是按最复杂的样例来计算复杂度的。

实际情况，leetcode 的数据样例很弱的，明确知道答案的贪心处理了，剩下的直接暴力搜索可以直接水过去的，简直不讲武德呀。

-）预处理判断是否有答案。
-）1 个集合，最大值减去最小值。
-）n 个集合，返回 0。
-）k 个集合，数字互不相等，从大到小平均分出 k 个集合即可。
-）2 个集合，相同的平分，剩下的按 k 个集合贪心。
-）其他，数据很弱，dfs 即可。

五、最后

这次比赛最后一题应该属于困难级别的，可能出题人想的数据比较弱以为是 dfs 搜索题，被标记为中等了。

做了最后一题，学到了一种高效的枚举子集方法，还学到了怎么构造扫描线的状态，很有趣的构造方法。

对了，周六晚上我再次参加了 atcode 比赛。
这次题意都很清晰，除了第二题读错题看成无交集子串外，其他的一下都读懂了，可是实力有限，只做出了三道题。

发现一个现象，比赛前一天去锻炼身体，比赛的时候头脑会比较清晰，思路也比较灵活。
下次比赛前可以试试。

加油，算法人。

《完》

-EOF-

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