Leetcode 第155场比赛回顾

作者: | 更新日期:

这次比赛涉及到容斥原理和拓扑排序,触发了很多人的知识盲区吧。

本文首发于公众号:天空的代码世界,微信号:tiankonguse
原文地址:https://mp.weixin.qq.com/s/vc-QsIJ7rcst_Ch1EG5R2A

零、背景

这次比赛对我来说都不难,本来有希望进去前百名的。
可惜最后一题一开始想错方向了,浪费了半个小时。
等理解题意开始敲代码后,时间已经来不及了。

PS:最近在学习 go 语言,这次比赛的代码我赛后使用 go 重写了一遍。
大家如果不会 go 和 python 的话,建议都学习一下。
这两个语言是未来的主流语言。

一、数组内差值最小的二元组

题意:给一个互不相同的数组,求差值最小的二元组。
如果有多个,都输出。

思路:最小的间距肯定是有序数组相邻的差值。
所以先对数组进行排序,然后循环找最小的,并保存答案。

二、求第N个丑数

丑数定义:给一个集合,如果集合内存在一个元素是整数n的约数,那整数n就是丑数。

思路:典型的容斥原理。

但是容斥只能找到一个数字 N 之内有多少个丑数。
想找到第n 个丑数,就需要进行二分了。

三、分组排序

题意:给一个字符串,以及一些索引二元组 。
索引二元组对应的值无限次数交换,求交换后字典序最小的字符串。

思路:二元组可以构造出一张图,这张图有多个联通分支(一个联通分支就是一个联通图)。
首先可以得出第一个结论:不同联通分支之间没有任何关系。所以独立计算每个联通分支即可。

然后有个不容易看出的结论二:不限交换次数的情况下,连通图可以得到所有顶点的任何排列。
题意要求字典序最小,那直接贪心,对值和索引排序,然后从小到大一一赋值即可。

证明:联通图是一个图,可能有环,我们删除一些边,使得图变成一颗树(是连通图的子集)。
然后从叶子节点触发,希望叶子节点的值是什么,就按照树的路径交换过来,删除叶子节点。
这样进行下去,只剩顶点的时候,我们就构造出了任意的排列组合。

总结:
第一步根据二元组构造一个图。
第二步对字符串进行分组,并排序得到答案。

四、二维拓扑排序

题意:给n个小组和m个项目,现在需要对项目排序 。
要求1:相同小组内的项目需要连续。
要求2:项目之间需要满足依赖关系(谁必须在谁前面)。

思路:典型的拓扑排序问题,即有向图是否有环问题。

那怎么进行拓扑排序呢?
自己画张图就很容易理解。
遍历入度是 0 的顶点并删除,删除顶点的时候,可能涉及到几条边。
这些边对应的顶点的入度都需要减一。
如果对应的顶点减一之后,入度变为 0,那就又找到一个入度为0的顶点。

就这样不断进行下去,直到找不到入度为 0 的顶点。
此时,如果删除的顶点个数 与 图的顶点个数不相等,说明有环,即不能拓扑排序。
而删除入度为0 顶点的顺序,就是排序后的答案。


再来看题意,小组内的项目要连续,那意味着小组之间也有个依赖关系。
这个依赖关系是根据项目的依赖关系以及项目所在小组聚合出来的。
构造出小组间的依赖关系后,进行拓扑排序,如果可以排序,再接着往下看。

如果小组间没有冲突,组内项目之间也可能有依赖关系。
所以组内的项目也需要进行一次拓扑排序。
排序的时候,就构造出了答案。

总结:
第一步,构造小组的依赖关系和组内项目的依赖关系。 第二步,判断小组间是否有冲突,没冲突计算出小组的拓扑排序。
第三步:判断每个小组内项目是否有冲突,没冲突计算出小组内项目的拓扑排序。

这个代码比较长,这里就不贴代码了。
感兴趣的可以点击原文查看源代码。

五、最后

赛后在 QQ 群里说这次比赛比较简单时,群友说其实不简单,做出三题就可以进前两百名了。

我回头一看,还真是。
一想,第二题容斥原理、第三题连通图贪心、第四题拓扑排序不是一般人会的,毕竟属于非主流算法。
这种题其实第一次遇到不会很正常,做过一次之后就大概知道,再遇到差不多就会了。

-EOF-

本文公众号:天空的代码世界
个人微信号:tiankonguse
QQ算法群:165531769(不止算法)
知识星球:不止算法

本文首发于公众号:天空的代码世界,微信号:tiankonguse
如果你想留言,可以在微信里面打开下面的地址进行留言。如果下面没有地址,可以关注公众号留言。
原文地址:https://mp.weixin.qq.com/s/vc-QsIJ7rcst_Ch1EG5R2A

点击查看评论

关注公众号,接收最新消息

关注小密圈,学习各种算法

tiankonguse +
穿越