Leetcode第三次双周比赛回顾

栏目: 编程工具 · 发布时间: 4年前

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

零、背景

很早之前,我就看到 Leetcode 曾发起了一个投票,说是要举办一个双周比赛。

当时我也是第一时间发到我的 QQ 算法群里。

Leetcode第三次双周比赛回顾

不过看时间,不是很好。

是双周的周六晚上,那时候我的时间已经计划做其他事情了。

所以我一直没有参加这个比赛。

周四晚上,一个微信好友问我,某某题怎么做。

一看,是 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) 的判断是否有重复字符。

Leetcode第三次双周比赛回顾

三、彼此熟识的最早时间

题意:有 N 个人,如果 AB 认识, BC 认识,我们认为 AC 也认识。

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

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

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

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

Leetcode第三次双周比赛回顾

四、得分最高的路径

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

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

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

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

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

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

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

Leetcode第三次双周比赛回顾

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

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

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

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

五、最后

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

-EOF-


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

CGI 程序设计自学通

CGI 程序设计自学通

(美)格里高利 / 徐丹/等 / 机械工业出版社 / 1998-08 / 28.00元

本书集中讨论CGI编程,以便利用一起来看看 《CGI 程序设计自学通》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

随机密码生成器
随机密码生成器

多种字符组合密码

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具