Leetcode 第143场比赛回顾

零、背景

这次比赛的题目相对比较简单，我在一个小时左右全部做完了。

赛后看了一下我每道题的耗时，发现一个有意思的现象。

通过时间  耗时  
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 ，摆不下时可以摆在下一层。

每层的高度为当前层所有书的最大高度，问书该如何摆才能使得总高度最小。

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

当然，这个思路使用递归实现就是 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-