leetcode 第 327 场算法比赛

作者: | 更新日期:

最后一题状态机有点复杂。

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

零、背景

这次比赛前三题很简单,最后一题有点复杂。

一、正整数和负整数的最大计数

题意:问数组中正整数的个数与负整数的个数谁多。

思路:循环统计比大小即可。

二、执行 K 次操作后的最大分数

题意:给一个数组,每次可以选择一个数字当做得分,然后数字的值变为原来的 1/3。
问如何选择数字,才能使得得分最大。

思路:贪心,维护一个最大堆,每次选择最大的值即可。

三、使字符串总不同字符的数目相等

题意:两个字符串可以交换一个字符,问交换后是否可以使得两个字符串出现的不同字符个数相等。

思路:先按字符聚合统计,数据范围就降低为 26 以内。
然后枚举交换的字符,判断是否满足答案即可。
复杂度:O(26^3)

注意事项:千万不要自己模拟各种情况,比如不同字符相等时是否满足,差一个是是否满足,差两个时是否满足。
由于存在很多边界,最终写出代码的话需要花费很多时间,还很容易漏。

四、过桥的时间

题意:有 n 个箱子在旧仓库,现在 k 个工人按照规则将箱子从旧仓库搬到新仓库。
路线中有一个独立桥,同一时间只能有一个工人过桥,题目告诉你一个谁先过桥的优先级规则。
每个工人有四段行程的时间:

新仓库到新仓库河岸的往返时间  
新仓库河岸出发的过桥时间  
旧仓库河岸到旧仓库的往返时间  
旧仓库河岸出发的过桥时间  

问旧仓库的箱子全部过桥后,最后一个箱子到达河新仓库河岸的时间。

思路:典型的状态机模拟题目,需要维护几个数据结构,且都是使用堆实现。

1、新仓库河岸上桥的等待队列。
2、旧仓库搬运过程中的未来时间线事件列表。
3、旧仓库河岸上桥的等待队列。
4、新仓库搬运过程中的未来时间线事件列表。

然后维护一个当前时刻,遵循时间线来模拟整个过程。

模拟过程如下:

0、检查箱子是否全部搬运,旧仓库上桥队列是否为空,旧仓库未来时间线事件列表是否为空,都空时结束。
1、检查未来时间线的事件列表中是否有事件小于当前时刻,有的话全部处理。
2、规则2:检查旧仓库等待上桥的队列,非空,选择一个过桥。
此时,时间线前进到过桥后,过桥的工人进入新仓库未来时间线事件列表,回到步骤0。
3、规则1:检查新仓库等待上桥的队列与箱子个数,有箱子且队列非空,选择一个过桥。
此时,时间线前进到过桥后,过桥的工人进入旧仓库未来时间线事件列表,回到步骤0 4、此时规则1与规则2都未不满足,代表没人等待过桥,都在搬箱子的路上。
此时,时间需要快进到两个未来时间线事件列表中最近的时间点。

复杂度:O(4n)

注意事项:题目要求的是最后一个箱子过桥即可,不需要工人搬到新仓库再回到河岸。

五、最后

这次比赛第三题很容易陷入误区,自己去根据不同字符个数来分析是否满足,从而发现边界有很多种。
而最后一题,则属于模拟题,有一定的难度,需要维护四个堆才行,再加上有一个注意事项,算是一个坑。

这次比赛你做了几道题,最后一题你是怎么做的呢?

加油,算法人。

《完》

-EOF-

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

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

点击查看评论

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

tiankonguse +
穿越