Leetcode 第143场比赛回顾

作者: | 更新日期:

这次比赛和上次一样,有一道语法分析的递归题,你可以来试试。

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

零、背景

这次比赛的题目相对比较简单,我在一个小时左右全部做完了。
赛后看了一下我每道题的耗时,发现一个有意思的现象。

   通过时间  耗时  
1. 0:18:52   18:52  
2. 0:36:27   17:35  
3. 0:50:59   14:32  
4. 1:06:28   15:29  

比赛的题从前到后是越来越难的,但是前面的题我反而耗时更多,后面的题耗时更少。
这个说明思考题花费的时间不多,敲代码的时间比较多,时间都花在敲代码上了。

当然这个也不完全正确,也可能边敲代码边思考,或者最终调试了很长时间。
还有一种可能是我选择了一种比较复杂的算法,其实有比较简单的方法。

对于耗时到底浪费在哪里了,这个只能使用一个录屏软件录下整个过程,然后分析一下才能真实的知道时间都花在哪里了吧。

下面来看看这四道题吧。

一、分糖果 II

题意: 给n个糖果,循环分给m个人,每次分的糖果个数加一个。
问每个人得到的糖果个数。

思路:由于规则固定,所以每个人得到的糖果也是固定的。
我们可以按规则画出每个人得到的糖果个数。

       1        2  ...        m
     m+1      m+2  ...      m+m
    2m+1     2m+2  ...     2m+m
                   ...
(k-1)m+1 (k-1)m+2  ...  (k-1)m+m
    km+1     km+2  ...  km+left

如上图表。可以看出来,每个人得到的糖果一次是x, x+m, x+2m, ... x+(k-1)m个。
对于前k行,每个人得到的糖果个数是等差数列,可以计算出来。

那怎么求出k呢?
第一个方法是解方程。
第二个方法是二分。

求出k之后,就可以先求出前k行,每个人得到多少糖果。
而剩余的糖果,可以在m人内分完,所以模拟即可。

赛后,看别人解题报告,发现很多人直接暴力做的。
由于每次分的糖果个数加一,那顶多分sqrt(n)次糖果。
虽然n比较大,但是开房后,就比较小了,所以暴力没有问题的。

二、二叉树寻路

题意:给一个二叉树,偶数层数字是反转的。
给一个数字,求输出这个数字到根的路径。

思路:可以计算出对应层的数字范围,根据当前层数以及第几个,就可以根据奇偶性计算出对应的值。
如果当前层数是奇数,则正常计算,即数字范围起始值加上偏移量。
如果当前层数是偶数,则逆序计算,即数字范围的结束地址减去偏移量。
使用这种方法需要注意一点,起始位置label是值,我们需要先计算出在二叉树中的真实位置,然后再模拟计算。

还有一种方法是假设输入label就是真实位置,每向一层,我们反转一次,这样则不存在上述的注意问题了,代码实现也比较简单。

三、填充书架

题意: 给n本书,每本书有一个厚度和高度,摆在书架上。
书架每一层最大宽度是shelf_width,摆不下时可以摆在下一层。
每层的高度为当前层所有书的最大高度,问书该如何摆才能使得总高度最小。

思路:经典的动态规划题。

定义dp[i]为前i本书能够到达的最小高度。
则对于第i+1本书,有若干选择。
如自己单独一层,则状态转移为dp[i+1] = dp[i] + h[i+1]
如果和前面的书放在一起,则状态转移方程式dp[i+1] = min(dp[j] + max[h[j+1] ~ h[i+1])), 其中需要满足sum(w[j+1] ~ w[i+1]) <= shelf_width,含义是前j本书组成若干层,第j+1到第i+1本书组成一层。
对于这些选择,取最小值。

当然,这个思路使用递归实现就是DFS加记忆化搜索了。
所以也有人说自己使用DFS过得,这个背后的逻辑其实是一样的。
只是一种是push down,一种是push up而已。

四、解析布尔表达式

题意:给一个布尔表达式的规则,求表达式对应的值。

这道题其实和上周比赛《Leetcode 第142场比赛回顾》最后一题非常类似。

布尔表达式有5个规则。

1. t 为真  
2. f 为假  
3. !(expr) 取反  
4. &(expr,expr,...) 取与  
5. |(expr,expr,...) 取或  

我们可以增加另外一个规则,就可以形成递归闭环。

6. `(expr,expr,...)` 获得布尔表达式集合。  

有了第6个万能的规则,代码实现就非常简单了 看一下求集合的目标后,我们发现并不需要求出整个集合,只需要统计是否有true和是否有false即可。

当然,实际比赛的时候,我直接计算出括号表达式里面的结果了。

赛后,看到一种解决方案:使用简单的替换转化为某种解释性语言的表达式,然后使用eval运算出结果来。
不过对于C++语言就不能这样做了。

五、最后

这次比赛涉及简单计算、二叉树、动态规划、递归题四种体型。
其实最后一题在专业比赛中属于模拟题,归属于简单题分类。
毕竟对于代码能力稍微强一点的人来说,递归都是不在话下的。

-EOF-

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

点击查看评论

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

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

tiankonguse +
穿越