leetcode 第 266 场算法比赛

作者: | 更新日期:

这题出的,该通过的算法被卡超时,暴力的方法直接过了。

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

零、背景

这次比赛题目该怎么办说呢?

第三题 n log(n)的方法被卡超时,浪费不少时间重新敲另外一个方法。
第四题花了不少时间做剪枝优化并通过,赛后优化都删掉,暴力 Dfs 竟然也通过了。

一、统计字符串中的元音子字符串

题意:给一个字符串,问由纯元音字母组成且包含所有元音的子字符串个数有多少个?

思路:数据范围不大,双层循环枚举所有子串即可。
复杂度:O(n^2)

优化:对于每个双元音连续子串,使用双指针快速判断满足要求的子串个数。
复杂度:O(n)

二、所有子字符串中的元音

题意:给一个字符串,问所有子串中,元音字母出现的次数。

思路:原问题是求所有子串所有元音出现的次数。
可以分别求每个位置的元音在哪些子串中出现过,所有位置的元音出现的次数之和就是答案。

一个元音出现的子串为左半部前缀的个数乘以右半部后缀的个数。
复杂度:O(n)

三、分配给商店的最多商品的最小值

题意:给 m 种类的商品,每类有若干个。现在需要把所有商品分配给 n 个商店。
每个商店只能分一类商品,问怎么分配,才能使得分配给商店的最大商品个数最小。

思路:我简单一分析,发现一个优先队列的贪心方法。

策略:默认把 m 个商品分给 m 个商店,即每个商品只分配给一个商店。
如果还有剩余商店,取平均分分配后,商品个数最多的那个商品,这个商品的商店个数加一,平均均就可以变小了。
这样不断的把商店分配给商品,最终就可以使答案最优。

时间复杂度:O(n log(n))
内存复杂度:O(m)

这个敲完后超时了,显然是因为内存操作太多,常数太高,被卡内存了。

回头一想,求最大值的最小值,显然使用二分查找可以做。

然后就把代码都删了,二分最优值,求出最少需要的商店个数,几行代码就写完了。
时间复杂度:O(n log(maxVal))
内存复杂度:O(1)

思考:猜测被卡超时的另一个原因是 leetcode 数据样例的 maxVal 都比较小,商品和商店的个数比较多。

四、 最大化一张图中的路径价值

题意:给一个无向图,每个边有一个时间代价,每个顶点有一个价值。
问从 0 出发,在 maxTime 时间内返回 0 时,经过的顶点的最大累计价值。

思路:数据上有两个突破口。

第一是:每个节点 至多 有 四条 边与之相连。
这意味者暴力计算时,每次顶多分叉四次。

第二是时间范围都在 [10, 100] 之间。
这意味者去在回来,顶多有 10 跳。

分叉四次,10 跳,复杂度就是 O(4^10),不会超时。

leetcode 的复杂度是最让人搞不懂的,我怕被卡超时,就进行剪枝优化。
预处理每个节点到 0 节点的最低耗时,这样枚举过程中,先判断是否可以在时间范围内返回 0 点。

PS:所有题通过后,我把剪枝删除后,暴力的代码只有几行,依旧可以通过。

五、最后

这次比赛第三题贪心是挺不错的策略,却被卡超时。
最后一题剪枝本来是个好思路,结果暴力就可以过。

打 Leetcode 比赛的时候,到底要不要优化真的把握不准,就像抽奖一样。
对于要不要优化,你有什么经验要分享的吗?

加油,算法人。

《完》

-EOF-

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

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

点击查看评论

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

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

tiankonguse +
穿越