leetcode 第189算法比赛

零、背景

这次继续在中文 leetcode 上做算法比赛。

前三题比较水，第四题几何题我又恨又爱。
恨她是因为几何体各种坐标，写起来非常繁琐，而且大部分计算都有模板。
爱她是因为作为 acmer ，虽然繁琐但还是可以做出来，而非 acmer 则从来没见过这些题，这对 acmer 算是一个优势。

做 leetcode 久了，总结出一个心得来。
这次使用这个心得做题排名是 52，比之前好多了。
在最后面分享一下这个心得，绝对有用，使用后解题速度可以得到大大提升。

下面来看看这次比赛的四道题吧。

一、此刻在做作业的人数

题意：给一些学生做作业的时间区间，问某个时刻还在做作业的人数。

思路：循环比较时间是否在区间内即可。

复杂度：O(n)

二、重新排列句子中的单词

题意：给一个字符串句子，按照单词长度对单词进行排序。

要求1：句子第一个字母需要大写。
要求2：排序时，相同长度的单词保持原来的相对顺序。

思路：拆分句子为单词列表，根据长度有序排序即可。

注意事项：预处理把句子第一个字母转换为小写，返回答案前再把答案的第一个字母转换为大写。

当然，之前我没使用过有序排序函数 stable_sort，所以我使用 map 来实现有序排序的功能了。

三、收藏清单

题意：给一些清单列表，清单中有若干公司名词。求出那些不是子集清单的下标列表。
子集定义：如果一个清单中的所有公司都在另外一个清单中，则这个清单就称为子集清单。

思路：最原始的方法是暴力查询。

1、枚举所有清单 A
2、与其他所有清单 B 对比
3、枚举清单 A 中的所有公司 a
4、在清单 B 的公司列表中判断 a 是否存在
5、如果存在一个 B，子公司包含 A 的所有子公司，则清单 A 不是答案。

复杂度：O(n2 * m2 * k)
n 为清单个数
m 为清单内公司的个数
k 为公司名称的个数

这个方法应该就可以过了。

当然，我写代码的时候，多花了几分钟做了几个优化。

1、公司编号化，这样比较公司就是一个数字比较。
2、公司列表 set 化，这样判断公司是否存在只需要 log(m) 的复杂度。

预处理复杂度：O(n^2 * log(m))
计算复杂度：O(n^2 * m * log(m))

四、圆形靶内的最大飞镖数量

题意：给若干坐标点好而一个半径，求寻找一个圆心，使得这个圆覆盖的点最多。

坑：题目并没有说圆心不固定的，不过看样例可以推测出这个题意。

思路：本来想二分，发现没法拆分子问题，放弃二分。

我们换个思路。
假设我们已经找到一个最优圆心，此时应该有几个点刚好在圆上，也就是这些点唯一确定了这个圆心。
如果输入的半径是无限大的，那也无所谓，我们只需要求出最优的圆心和半径即可。

想到这里，那只需要枚举可能的圆心即可。

那什么时候可以唯一确定一个圆心和半径呢？
最显然的是不在一条直线上的三点确定一个圆。

容易忽略的一个是两点在直径对角线上时，也可以确定一个圆。

这两种都想到了，那就是枚举所有的直径和三角形，找到圆心，计算答案即可。

五、最后

前面提到，我比赛久了，总结出一个心得来。

这个心得实际上去年在《专业选手与业余人员的差距》分享过，当时重点介绍的是专业选手与业务选手的不同。

之前关于 leetcode 的一些认识没有展开讲，这里稍微展开说几句。

具体来说就是 leetcode 的定位不是一个算法竞赛网站，而是一个职场找工作网站。

这个也决定了 leetcode 比赛题不是为了考查非常高深的数据结构与思维能力，而是为了考查大家的数据结构基础知识、基础的分析能力、以及动手能力。

比如收藏清单，大家根据题意简单分析一下，都可以在心中想象出怎么计算。
动手能力强的人，心中想象出怎么算后（所谓的思路），能够快速的将想象变为实际的代码。

根据这个特点，前面的几道简单题在比赛的过程中就没必要去想最优解了。
比如 n 等于 100, 复杂度为 O(n^4) 在 leetcode 上不会超时。
我们想到可以通过树套树在O(n * log(n)^2)的复杂度实现，也不要这样走。
毕竟比赛的目的是通过这道题，不是找最优解。

这样，比赛过程中，对于前面三道题，都可以无脑按最基本的方法去实现，一般都可以通过。

而如果对更优的解法感兴趣，可以赛后再去研究实现一下。

《完》

-EOF-

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