leetcode 第 290 场算法比赛

作者: | 更新日期:

五一调休加班,没参加比赛,看榜单太恐怖了。

本文首发于公众号:天空的代码世界,微信号:tiankonguse

零、背景

这次比赛恰好遇到五一调休加班,所以就没参加比赛。

中午看了下题,发现这次比赛很恐怖,第一名只用了三分钟就做完了四道题。

那说明题目很简单,我便在午休之前做了一下四道题。

后两道题是模板题,如果模板准备好的话,几分钟就可以通过吧。

一、多个数组求交集

题意:给 n 个数组,每个数组中数字互不相同,问哪些数字在所有数组中都存在。

思路:map 统计所有数字,出现个数为 n 的数字就是答案。

思考题:数组中有重复数字,又该如何做呢?

二、统计圆内格点数目

题意:给 n 个圆的圆心和半径,问在圆里面的整数坐标个数。

思路:枚举每个圆内的整数坐标,去重即可。

对于每个圆,假设圆心是 (x, y),半径是 r,则枚举 [x-r, y-r][x+r, y+r] 正方形内的所有点,判断是否在圆内即可。

三、统计包含每个点的矩形数目

题意:给 n 个左下角为 (0, 0) 的矩阵,问 m 个坐标分别在几个矩阵内。

思路:假设矩阵是任意的,则可以通过双指针来解决。
这里所有矩阵的左下角固定,所以只需要一个右指针即可处理这类问题。

PS:题目保证矩阵和询问互不相同,其实相同也不影响。

维护一个数据结构,储存下所有矩阵的高度。
给一个坐标 (x, y), 假设 x 确定在所有矩阵内,问题就转化为了求矩阵高度大于等于 y 的个数。

面对这种问题,一般使用线段树或树状数组来解决。
坐标值很大,提前预处理离散化即可。
这样问题就转化为了询问区间和。

那不满足所有矩阵都覆盖 x 改怎么办呢?
如果我们能够找到素有不满足的矩阵,从数据结构中删除就可以了。

所以,这时候就需要双指针技术了。
先对矩阵进行排序,每次询问前,先删除不满足的矩阵,然后再询问即可。

注意事项:由于有多组查询,所以查询也需要排序,从小到大来询问,再结合双指针,就可以做到 n log(n) 的复杂度了。

思考题:矩阵左下角不为原点,该如何做呢?

四、花期内花的数目

题意:给若干线段,问指定点,被哪些线段覆盖。

思路:

每个线段,可以理解为区间全部加一。
问点被哪些线段覆盖,就是单点查询。

所以,这道题比第三题还简单。 不需要更新操作,初始化数据结构后查询即可

五、最后

这次比赛没意思,不过我发现我的线段树模板有问题,需要调整下我的模板了。

具体来说,需要提前把最大值、最小值、区间和都准备好,这样以后就可以直接使用了。

加油,算法人。

《完》

-EOF-

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

本文首发于公众号:天空的代码世界,微信号:tiankonguse
如果你想留言,可以在微信里面关注公众号进行留言。

点击查看评论

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

tiankonguse +
穿越