leetcode 2020春季算法比赛

作者: | 更新日期:

这次比赛有点ACM的味道。

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

零、背景

2020年4月18日参加了 leetcode 举办的 2020年春季算法比赛。

结果比赛期间有人来看房子。

原因是我在深圳合租的房子有个室友抽签抽到公租房,搬出去了。
几个同事预约这天下午来看房,只能抽一段时间做几道题了。

比如在三点半的时候,有个同事过来了。

五点左右,又有个同事来看房。

这看房大概浪费了一个小时半,我这敲代码速度,题肯定做不完了。

不过我还是尽量的去做题,做了三道题,看排名是第 88 名,没进去前 50 名,比较遗憾。

PS:刚开始比赛时我随机看的第四题,一看大水题,敲完发现提交后提示看不懂,多点了几下提交,被罚两次。
后来只能从第一题开始做,做到后面再重写第四题被卡时间了, map换成unorder_map 就过了。

下面来看看这些题吧。

一、拿硬币

题意:有 n 堆硬币,每次可以从一堆中拿1个或者2个。
问最少需要拿几次?

思路:每堆独立。

对于每一堆,肯定是尽量拿两个,如果到最后还剩一个就只能拿一个。

使用数学语言就是偶数除2,奇数除2向上取整。
合在一起就是每堆除2向上取整,然后求和。

二、传递信息

题意:给一个有向图,起点在 0, 每次可以选择一条边进行移动。
问移动 k 次后到达节点 n - 1 的路径数。

思路:动态规划题,我喜欢的题型。

暴力方法:
每移动一步,统计所有顶点为当前终点的路径数。
复杂度:O(k n^2)

矩阵幂方法:
构造状态矩阵策略:如果一个点 i 到另一个点 j 有边,则置 matrix[i][j] = 1。
其实状态是 [1, 0, 0, 0, 0]
复杂度:O(n^3 log(k))

由于这里 k 比较小,所以没必要 标准做法是矩阵幂来做,但是这道题作为第2题,数据样例弱爆了。
所以直接暴力做就行了。

三、剧情触发时间

题意:给一些三个属性值,每天三个属性值都会增长,增长多少输入参数会告诉你。
如果三个属性值都大于某个剧情的最小依赖属性值,则这个剧情可以解锁。
问:哪些剧情可以解锁,如果可以解锁,剧情输出在第几天解锁的,都在输出-1。

思路:有两个思路来做这道题。

一种是每天计算当前属性值,然后查询可以解锁哪些剧情。
假设有 n 天,m 个剧情。
复杂度:O(n m),会超时。

另一种是提前计算好每天的属性值,然后拿着每个剧情来二分查找可以在哪天首次解锁。
复杂度:O(m log(n))


四、最小跳跃次数

题意:给一个大小为 n 的数组 arr 。
如果我们在某个位置 i 时,可以向左跳到任意位置,向右可以调到 i+arr[i] 位置。
问最少需要多少步跳的位置可以大于n。

思路:大水题,之前做过无数次了。
一个队列搞定。

使用队列记录需要跳的位置以及跳数,使用一个map标记某个位置是否跳过。
死循环遍历队列,判断是否可以跳出去,可以了结束。
不可以了则把左边未跳的位置加入队里,右边的i+arr[i]加入队列即可。
复杂度:O(n)

五、二叉树任务调度

题意:给一个二叉树,节点的值点当前节点需要执行的CPU时间。
给两个CPU,同一个节点同一时间只能由一个CPU执行。
不同节点可以并发执行。

不过这里有个条件限制:一个节点的左右儿子都执行完的时候,才能执行当前节点。

这道题不好想,我们分两步来看这道题。

假设我们已经有最优解了,CPU也分配好了。
此时翻转一下题意,换成左右儿子必须等待父节点执行完。
题意翻转后,发现最优解不变。

所以第一步是翻转题意,把父亲依赖儿子转换成儿子依赖父亲。
这样我们就可以从上到下递归了。

接着,递归就需要对一棵树求两个值了。
一个值是可以并发运行的总时间,一个是只能独立运行的总时间。

假设左右儿子都求完这两个时间,那当前树的时间能不能求出来呢?
貌似还真可以。

我们需要判断左右儿子能否存在独立运行时间。
只有一种情况会存在,那就是一个儿子的独立时间大于另一个儿子的所有时间。
否则,我们可以先把左右的独立时间并发掉,然后可以并发的正常并发即可。

一个树的独立时间和并发时间计算出来之后,答案就是独立时间加上并发时间的一半。

六、最后

赛后看看这次比赛,体验挺差的。

首先入口不好找,也不能看榜单,也不能看自己哪些题过了那些题没过。

不过题目是好题目,动态规划遇到矩阵幂,二分查找、队列搜索等。
而对于最后一题,不会就算了,这种确实不好想。

《完》

-EOF-

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

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

点击查看评论

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

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

tiankonguse +
穿越