leetcode 第 276 场算法比赛

作者: | 更新日期:

三道贪心题,最后一题果然需要碰运气。

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

零、背景

这次比赛有点意思,最后一题二分贪心做的,正确性大概证明了下,但是还是不确定。
看下榜单,过的人很多,那就确定贪心不会有问题了,提交了一下,就过了。

一、将字符串拆分为若干长度为 k 的组

题意:给一个字符串,要求分隔为长度固定为 k 的子字符串,最后不足的补充一个默认字符。

思路:按照题意,两层循环复制即可。

小技巧:先计算出填充后的总长度,对输入进行 resize ,填充值就为默认值。
之后使用 substr 子串一层循环就可以直接得到答案。

二、得到目标值的最少行动次数

题意:给一个起始数字 1,可以执行两个操作:加一或者翻倍。
翻倍次数有限制,问最少执行多少次操作可以得到一个目标数字。

思路:可以证明,想要次数最少,翻倍执行的越晚越好。

所以可以贪心逆向反推,可以减半就减半,不能减半再减一。
如果减半次数用完了,那剩下的都是减一。

三、解决智力问题

题意:给一个数组,每个位置有两个值,分别代表分数与跳数。
分数是可以获得的积分。
跳数是选择当前分数时,未来的连续若干条需要跳过。
问从前到后扫描,怎么操作才能获取最高分。

思路:动态规划题,或者贪心题。

对于每个位置分为选择或者不选择。

我们可以使用一个数组标记每个位置之前已经获取的分数。

到达一个位置后。

如果选择,得到就是起始分加当前分。
若干跳之后的位置的起始分也可以得到刷新。

如果不选择,则下一个位置的起始分可以继承当前位置的起始分。

这样从前到后扫描一遍,就可以得到最大分。

四、同时运行 N 台电脑的最长时间

题意:给 m 个电量独立的电池和 n 个电脑。
每个电脑可以装一个电池,有电量的情况下可以持续运行。
每个整数时间点可以换任意的有电量的电池。而且换电池的时间可以忽略。
问所有电脑持续运行的最大时间。

思路:由于换电池的时间都是整数,所以每次换电池的时候,至少需要运行一个单位。

纸上随便画几个例子,很容易发现,一般情况下所有电池都可以把电量用完,直到最后电量无法支撑 n 个电脑再运行一分钟。

当然,也存在一种极端情况:如果一个电池电量非常大,其他电池电量非常小时,不能简单的使用上面的贪心。

综合上面两种情况,发现二分枚举最终运行时间,判断是否满足这个时间即可。

这样,对于电量非常大的电池,通过枚举的答案,可以特殊处理掉。
剩余的电池再使用上面的贪心来处理即可。

复杂度:O(n log(n))

当然,可以适当的预处理下数据,应该可以做到 O(log(n) log(n)) 的复杂度。

五、最后

这次比赛竟然除了三道贪心题,第二题是数学贪心题型,第三题是动态规划贪心,第四题是二分贪心。

这三道贪心题你都是怎么做的呢?

最后一题的贪心方法你能证明吗?

《完》

-EOF-

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

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

点击查看评论

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

tiankonguse +
穿越