Leetcode第三次双周比赛回顾

零、背景

很早之前，我就看到 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 个人，如果 A 和 B 认识， B 和 C 认识，我们认为 A 和 C 也认识。

接下来的一段时间内，不断的有两个人认识，问最终是否所有人都互相认识。

如果都互相认识，输出首次互相认识的时间点。

思路：这个是经典的并查集问题。

按照时间不断的合并联通图，当全联通的时候，输出时间即可。

四、得分最高的路径

题意：给一个矩阵，从左上角到右下角的路径考虑有很多条。

一条路径的分数定义为当前路径上节点的最小值。

矩阵的最优值定义为所有路径里最大的那个分数。

思路：对于最优值问题，前面已经介绍过，使用 BFS 搜索即可。

这道题里面，路径上的节点由两部分组成：坐标与当前路径的分数。

所以我们 BFS 的时候，根据上面的两部分来进行搜索。

当遇到已经搜过的坐标时，需要判断分数是否更优，更优的话需要入队继续搜索。

其实，我们可以发现，在搜索的时候做了很多无用功。

因为是 BFS ，后来有更优的点时，也需要等前面的出队才能处理后面的。

所以可以使用 优先队列来优化。

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

五、最后

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

-EOF-