leetcode 第188算法比赛

零、背景

有几周没参加比赛了。

记得刚有 leetcode 中文网站的时候，我就去使用了下，结果比赛被中文错误的翻译坑了几次，就再也不在中文 leetcode 做比赛了。

现在已经过了几年了，这些问题 leetcode 中文网应该都解决了。

另外中文网站有一个好处，就是网站速度比英文快，而且题目阅读起来也轻松很多，那为什么不来中文网站呢。

这周开始，我准备在中文 leetcode 上做比赛，在中文 leetcode 上做题。

好了，接下来看看这次比赛的题目吧。

一、构造数组

题意：给一个有序的目标数组栈，有一个输入流，依次从1~n返回一个数字，问怎么构造出目标数组。
输入流操作：我们可以把输入流的数字入栈目标数组，也可以选择出栈。
如果已经构造出目标数组，则可以结束。
求入栈出栈的操作序列。

题目比较抽象，看个例子就懂了。

假设目标数组是1,3，输入流是1~4。
第一次来的是 1，入栈 push。
第二次来的是 2，入栈 push，由于目标数组不需要 2，需要再次 pop 出栈。
第三次来的是 3，入栈 push。
构造出目标数组了。

思路：

每次比较当前输入流的数字是否需要保留在目标数组中，不需要则 push 和 pop 二连操作。
需要保留在目标数组中，则只 push 即可。

二、三元组数目个数

题意：给一个数组，问是否存在三个下表i<j<=k，使得 XOR(i,j-1) 与 XOR(j, k) 相等。
XOR(x,y) 含义是 x 到 y 之间的数字进行异或操作。

分析：

异或的第一个性质：相同的值异或后为 0。
异或的第二个性质：满足结合律，即 (a ^ b) ^ c 与 a ^ (b ^ c) 相等。

这两个性质可以推出一个结论：对于任意 j, XOR(i, j-1) ^ XOR(j,k) 都和 XOR(i,k)相等。

由此，我们如果找到一个XOR(i,k)为0，则可以拆分为 k-i个 j 构造出三元组。

这样，我们只需要找到所有的二元组 (i,k)，使得XOR(i,k) 为0，然后使用上面的公式计算出有多少个三元组即可。

坑：我看错题意了，看成i<j<k了，花费不少时间。

三、收集苹果的最少时间

题意：给一个无向树，某些节点上有苹果。
求从 0 节点出发，把所有苹果摘掉后，再返回 0 节点的时间。
时间：每经过一条边，消耗 1 秒。

分析：DFS 即可。

注意1：如果某个儿子没有苹果，就没必要遍历那个儿子。
注意2：边下去和上来都消耗时间。

如果父节点下的某个儿子有苹果，父亲到儿子需要加上往返的代价。
那这个代价在哪里处理就需要作出抉择：

一种是儿子自己负责判断当前子树是否有苹果。
一种是父节点负责判断儿子是否有苹果。

我采用的是儿子自己判断。
此时注意事项是根节点没有父节点。

如果采用父节点判断，则需要额外增加一个变量来标记儿子上是否有苹果。

四、切披萨的方案数

题意：给一个披萨矩阵，需要将披萨切成 k 分，每份上至少有一个苹果。问有多少种切法。
规则：上下切的时候，只能切下面，上面的不能切。左右切的时候，只能切右边，左边不能切。

思路：标准的动态规划。

定义状态：f(x,y,k) 为子矩阵 (x,y) 分给 k 个人的答案。
则对于第一个人，枚举所有横着切和竖着切的方法，对于合法的方案求和即可。

合法的条件：第一个人切后有苹果，剩下的矩阵存在方案，分给 k - 1个人。

剪枝：如果矩阵剩余的苹果小于人数，那肯定不符合条件的。
出口：如果只剩一个人时，有苹果则存在一个方案，否则不存在方案。

五、最后

这次比赛我犯了不少错误。

第二题构造三元数组，我看错题了，浪费不少时间。
第三题摘苹果，来回我只算了一次时间，也算看错题了。
第四题则是手误，预处理时从后到前处理的，我的迭代器写成 ++ 了。

看来自己还是需要注意这些细节的，细节决定了我能不能进去前50 名把。

思考题：这次摘苹果和披萨题是否有遇到什么问题了吗？

《完》

-EOF-

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