Leetcode第三次双周比赛回顾

作者: | 更新日期:

有人问我搜索为什么超时,我说要记忆化搜索。

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

零、背景

很早之前,我就看到 Leetcode 曾发起了一个投票,说是要举办一个双周比赛。
当时我也是第一时间发到我的 QQ 算法群里。

不过看时间,不是很好。
是双周的周六晚上,那时候我的时间已经计划做其他事情了。
所以我一直没有参加这个比赛。

周四晚上,一个微信好友问我,某某题怎么做。
一看,是 Leetcode 双周第三次比赛的最后一题。

简单一看,就是记忆化搜索题,但是告诉他后,他还是不会。 于是我做了这场比赛,发现题目非常简单,属于简单题型。
现在来看看这些题吧。

一、小于 K 的两数之和

题意:给一个数组,问是否存在两个数之和小于 K,如果存在,则输出小于K的最大的和。

思路:由于数组大小最大是100,所以双层循环求出所有的和,找到满足条件的最大值即可。
复杂度:O(n^2)

那能不能优化一下复杂度呢?
还真可以。

先对数组排序O(n log(n)),然后枚举每一个数字A,然后二分查找第一个小于等于K-A的数字。
综合复杂度O(n log(n))

二、长度为 K 的无重复字符子串

题意:给一个字符串,对于所有长度为K的字串里面,求无重复字符的字串个数。

思路:对于长度为L的字符串,长度为N的字串有N-K+1个。
面对这些字串,如果一个个判断是否有重复字符的话,复杂度就是O(NK)
这种方法按理说会超时的。

实际上,上面的那种字串之间是有联系的。
比如相邻的字串,只是左边少一个字符,右边多一个字符。
如果下一个字串能够复用上一个字串的信息,那么时间复杂度就可以大大的降低了。
这种方法我们成为滑动窗口。

对于一个窗口,我们维护一个统计信息。
比如每个字符出现了几次,目前出现了几个字符。
这样我们在从上一个字串转移到下一个字串时,可以O(1)的转移,并且可以O(1)的判断是否有重复字符。

三、彼此熟识的最早时间

题意:有N个人,如果AB认识,BC认识,我们认为AC也认识。
接下来的一段时间内,不断的有两个人认识,问最终是否所有人都互相认识。
如果都互相认识,输出首次互相认识的时间点。

思路:这个是经典的并查集问题。
按照时间不断的合并联通图,当全联通的时候,输出时间即可。

四、得分最高的路径

题意:给一个矩阵,从左上角到右下角的路径考虑有很多条。
一条路径的分数定义为当前路径上节点的最小值。
矩阵的最优值定义为所有路径里最大的那个分数。

思路:对于最优值问题,前面已经介绍过,使用BFS搜索即可。
这道题里面,路径上的节点由两部分组成:坐标与当前路径的分数。

所以我们BFS的时候,根据上面的两部分来进行搜索。
当遇到已经搜过的坐标时,需要判断分数是否更优,更优的话需要入队继续搜索。

其实,我们可以发现,在搜索的时候做了很多无用功。
因为是BFS,后来有更优的点时,也需要等前面的出队才能处理后面的。
所以可以使用 优先队列来优化。

这个优化只是队列的性质发生了变化,而其他逻辑都没有变化,这里就不多说了。

五、最后

这个比赛涉及到滑动窗口、图论并查集、记忆化搜索等题,还是蛮基础的,感兴趣的可以做一下。

-EOF-

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

点击查看评论

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

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

tiankonguse +
穿越