leetcode 第 293 场算法比赛

零、背景

这次比赛本以为可以在 30 分钟内做完进入前百名，甚至冲刺下前 50 名。

结果最后一题算错复杂度了，错误两次。

一、移除字母异位词后的结果数组

题意：给一个字符串数组，如果存在相邻的异位词，删除后面那个，求最终的答案。

思路：扫描字符串，对字符串排序比较即可。

比赛的时候，想着直接边排序边求答案比较麻烦，便预处理出排序字符串，然后求答案。

结果发现预处理反而更麻烦。

二、不含特殊楼层的最大连续楼层数

题意：给一个可用的最低楼层和最高楼层，以及一些不可到达的楼层。
问剩余的楼层里，连续的可用的最多楼层个数。

思路：不可到达楼层排序，扫描一遍相减即可。

三、按位与结果大于零的最长组合

题意：给一个数字数组，求最长的子序列，使得子序列与运算后不为 0。

思路：逆向思维，既然子序列与运算不为 0，说明这些数字的某一位比特位都不为 0。

所以可以枚举比特位，分别找到某位比特位不为0的个数，求最大值即可。

四、统计区间中的整数数目

题意：交互题，两个操作：要么添加一个线段，要么问线段合并后的长度。

思路：看到线段合并，第一时间想到的是离散化线段树和map。
由于是交互题，无法离散化，所以只能使用 map 做。

添加一个线段的复杂度是 log(n)。
如果存在合并线段，累计合并 O(n) 次，均摊复杂度是 O(1)。
查询时，扫描 map，求和即可，单次复杂度 O(n)。

正常情况下，map 的 key 储存线段的左顶点，val 储存线段的右顶点。
合并时先 lower_bound, 然后依次判断前一个与后一个是否可以合并。

我突发奇想，map 的 key 储存线段的右顶点， val 储存线段的左顶点。
这样 lower_bound 查找之后只需要判断一次就可以知道是否可以合并。

于是便使用新发现的算法来敲代码，结果超时了。
我想，难道新的算法有漏洞，导致死循环？
于是赶紧使用旧的算法，敲完也超时了。

于是赶紧读题与计算复杂度，突然发现问题出在查询上。
单次查询复杂度是O(n)， n 次就是 O(n^2) 了。

于是赶紧把查询的答案，在合并线段时提前计算好，之后就过了这道题。

五、最后

这次比赛，第一次提交最后一题的时间是比赛开始后 28 分钟。
结果到第 38 分钟才通过。
加上两次罚时（每次扣 5 分钟），通过时间算 48 分钟了，排名又是一百名之后了。

看下榜单，发现大部分人都被这道题坑了。
这样看来，大家都不被坑，我还是进不了前百名吧。

加油，算法人。

《完》

-EOF-

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