Leetcode 第144场比赛回顾

作者: | 更新日期:

区间操作、树转森林、有效括号,都是不错的基础题。

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

零、背景

这次比赛相对简单,我花了 35 分钟就做完了。
可惜有个地方敲错了没有测试直接提交,RE了一次。

这次比赛时间就比较合理了,时间分别是2分、5分、14分、15分
但是最快的人是11分钟做完所有题,所以还需要加把劲,提高敲键盘的速度。

下面我们来看看这四道题吧。

一、IP 地址无效化

题意:对 IP 地址的.替换为[.]

思路:扫描一遍判断即可。

二、航班预订统计

题意:一条指令的含义是区间加上指定值,有很多指令,求最终区间每个位置的值。

思路:最原始的方法是线段树区间操作。

但是这道题不存在查询,只是求最终结果。
那就可以使用标记的方法,区间的开始位置加上指定值,区间结束的下个位置减去指定值。
然后从左到右累加即可。

三、删点成林

题意:给一个二叉树,节点的值互不相同。给一个集合代表这些树的节点要被删除。
一个数删除一个节点后,会形成多个树,称之为森林。
求删除节点后的森林(数之间顺序不做要求)。

思路:直接递归即可。

需要特殊处理的地方就是传递一个标记,代表当前节点是否可能是树根。
如果是树根的话,需要加入答案。不是树根的话,直接递归即可。

当然,比赛的时候,我是使用队列加递归实现的。
队列里面保存当前可能是答案的树。
如果当前树的根没有删除,则找到一个答案。
之后递归处理每一颗树,判断是否有子节点被删除,从而拆分出两颗树。

四、有效括号的嵌套深度

题意:需要先对有效括号与括号的深度的定义达成一致。
有效括号的定义:空字符串是有效括号,AB是有效括号,则AB(A)都是有效括号。
括号深度的定义:空字符串的深度为0AB的深度为max(d(A), d(B))(A)的深度为1 + d(A)

现在需要对一个有效括号进行拆分,拆分为两个有效括号,目标是拆分后两个有效括号的最大深度最小。
问该如何拆分?

拆分定义:从一个有效括号序列中删除一些字符,则剩余的可以组成一个有效括号,删除的字符也可以组成一个有效括号。

既然是为了最大深度最小,那就应该对深度对半分。
即如果一个括号的深度是2n,那拆分后的两个括号的深度应该都是n
同理,如果一个的深度是2n+1,那拆分后的两个括号的深度分别是nn+1

如果能够想到这里,这道题就很简单了。
对用栈来遍历有效括号序列,按照奇偶性,深度每增加一次,就打上删除标记。

而对于多个平行的有效括号,比如AB,第一个位置的标记需要不同。
不然对于()()我们就没有删除任何括号。

具体可以看代码

五、最后

这次比赛相对简单,涉及大水题字符串替换、线段树区间操作(贪心左加右减)、树拆分为森林、有效括号拆分四种题型。
树和有小括号这两道题还是比较考验代码能力的,你敢来挑战这两道题吗?

-EOF-

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

点击查看评论

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

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

tiankonguse +
穿越