【算法】Leetcode 第132场比赛回顾

一、背景

上周清明节回家了，没有做比赛。
这周继续开始做算法比赛，来给你们分享解题报告。

题目地址：https://leetcode.com/contest/weekly-contest-132
源代码：https://github.com/tiankonguse/leetcode-solutions/blob/master/contest/132

二、除数博弈

题号：1025
题目：Divisor Game

题意：告诉你一个数字N，以及一个游戏规则：选择一个数字x，且满足0<x<N && N%x==0，从而使得N=N-x。
两个人轮流进行这个操作，最后无法操作的那个人算输掉游戏。

思路：啊啊啊，终于出现博弈题了。
我最喜欢博弈题了。
因为我知道这个世界上大部分人是没有逻辑或者逻辑有问题的，而博弈题需要很强逻辑。
所以我可以依靠博弈题把那些人的差距拉开。
扯远了。

对于博弈论，其实最简单了。
只需要按照博弈规则，进行DFS即可。
而DFS的出口就是最小的输掉游戏的N，即N=1时是出口。

对于其他数字，只需要找到所有的因子（整除），判断这些因子是否会输掉游戏。
这里的关键逻辑是：只要有一个因子确定会输掉游戏，那当前数字肯定不会输掉游戏。

依靠这个关键逻辑，你应该就可以轻松实现代码了。

PS：当然，对于DFS显然存在重复计算问题，算过的你保存下来就可以了。

三、节点与其祖先之间的最大差值

题号：1026
题目：Maximum Difference Between Node and Ancestor

题意：对于一个树来说，每个节点都有很多祖先节点。
这个节点与祖先节点的最大差值也可以计算出来，称为节点祖先差值。
所有这些节点祖先差值里面的最大值，称为树的祖先差值。
求一个树的祖先差值。

思路：对于树来说，有天然的递归性。
递归的时候，只要带上当前祖先里面的最大值与最小值，即可算出当前节点的最大差值。
而一颗树的祖先差值为左子树的祖先差值、右子树的祖先差值、当前节点的祖先差值三个答案里面的最大值。

注：子树的祖先差值需要带上路径上的最大值和最小值。

四、最长等差数列

题号：1027
题目：Longest Arithmetic Sequence

题意：给一个数组A，求一个子序列，使得这个子序列是等差数列且长度最长。

思路：典型的动态规划题（DP）。
假设你已经计算出前面0~i-1这些位置为后缀的所有步长的最长等差数列，遍历这些数字，即可计算出i位置为后缀的所有步长的最长等差数列。

以k为例具体展开来说说（0<=k<i）。
由于A[i]-A[k]的值是固定的，所以你只需要获得以k为结尾步长为A[i]-A[k]的等差数列最大长度。
然后这个最大长度加一就可以得到以i结尾，步长为A[i]-A[k]的最大长度。

这里有个注意事项是：前面可能存在值相同的数字，此时A[i]-A[k]相同，此时会计算出多个答案，需要取最大值。

优化：在注意事项里面提到可能存在相同的值，需要取最大值。
简单分析一下，可以发现这个最大值肯定是最后一个A[k]。
所以如果你使用一个容器维护这些最优的A[k]，内存循环的遍历次数就可以大大减少。
当然最坏情况下一个也没减少。

复杂度：O(n^2)
PS：当然，比赛的时候，我是直接暴力层循环做得。

五、从先序遍历还原二叉树

题号：1028
题目：Recover a Tree From Preorder Traversal

题意：一个字符串是二叉树按照一定规则先序遍历输出的结果，现在需要根据这个字符串计算出二叉树。
规则：每次先输出节点的深度，再输出节点（当只有一个节点时，保证节点为左子字节）。

思路：按照题意，依次读取下一个深度和值，然后根据深度找到父节点，然后递归即可。

注意事项：
1.父节点的深度加一等于当前节点的深度。如果不满足说明父节点还在上一层，继续迭代即可。
2.找到父节点后，需要先判断左儿子是否存在。不存在当前节点为左儿子，存在则为右儿子。

六、最后

这次比赛的难度属于中等偏下水平，涉及博弈、动态规划、遍历树三种题型。
遍历树的含义是较简单的树，只需要DFS即可解决。

其中有两道题树的题，我是裸敲然后提交的。
因为本地还没有自动化测试的环境，赛后我已经把环境搭建好了。

不知道你有没有发现，如果输入参数是树时，你的测试将会很麻烦，需要构造出这个树。
使用我的自动化测试环境就没这个问题，可以自动构造出树来。
如果输出结果是树，也没问题，而且还可以自动化对比输出的树是否和答案一致。

公众号后台回复leetcode获取最新模板。

下面两张图分别是树是输入参数，以及树时输出答案时的样例。
如果答案错了，还可以打印出树来。

-EOF-