leetcode 第 282 场算法比赛

作者: | 更新日期:

二分算法与动态规划,永不过时。

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

零、背景

这次比赛怎么说呢,其实不难,最后一题我调试半天,算法没变,最终通过了。

原来是 Leetcode 升级了,全局变量必须每次都初始化才行。

一、统计包含给定前缀的字符串

题意:给若干字符串,求前缀等于查询字符串的个数。

思路:循环 strncmp 比较即可。

二、使两字符串互为字母异位词的最少步骤数

题意: 给两个字符串,可以分别对两个字符串插入字符,怎最少插入几个字符,才能使得两个字符串的字符集合相等。

思路:既然是集合比较,与顺序无关,统计两个字符串每个字符的个数,谁少补谁即可。

三、完成旅途的最少时间

题意:给若干公交车,每个车旅行一圈的速度是固定的。
所有车可以同时发车,问旅行 N 圈至少需要多少时间。

思路:正常思维是枚举时间,判断每趟车可以赚几圈,求和判断是否满足答案。

但是枚举会超时,所以需要二分。

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

四、完成比赛的最少时间

题意:给若干公交车,同一时间只能有一样车旅行。
每个车旅行一圈后,如果继续旅行,下一圈的耗时是指数级增长的。 如果换车,则下一圈的车耗时重新从初始值计算。
但是换车有一个代价,等待固定时间。
问旅行 N 圈的最小时间。

思路:这道题有点意思。

最初的思维是去对比:下一圈不换车与换车后下一圈选哪个会更优。
但是,简单推导后,发现换车时不仅需要考虑下一圈,还需要考虑下两圈,甚至下 N 圈。

所以我们需要预处理所有公交车,计算出每个公交车连续运行 N 圈的时间。
显然,对于固定运行 N 圈的公交车,我们只需要最小的那个。

另外,由于总耗时是 32 位整数内的,指数增长底是 2,所以 N 最大是 32。
所以我们只需要开一个大小为 32 的数组,计算出这些圈的最小耗时。

有了这个数据,就会发现这道题可以使用动态规划来做。

方程如下:

f(N) = minLoop(N)
f(N) = min(minLoop(i) + T + f(N - i))

方程含义是,枚举上一次换车后运行的圈数,求最优值。

注意事项:可能 N 很小,此时可以不换车。

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

五、最后

昨晚我开始做 atcode,尝试使用 C 风格使用全局数组来定义数据了。
结果 leetcode 顺手也定义为全局变量了。

leetcode 不止什么时候,不同测试数据会使用一个全局变量,这就导致全局变量未初始化的问题了。
调试了半个小时,发现是这个问题后,才通过这道题。

如果不被这个坑,感觉这次有可能进入前百名的。

加油,算法人。

《完》

-EOF-

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

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

点击查看评论

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

tiankonguse +
穿越