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-

我来评几句
登录后评论

已发表评论数()

相关站点

热门文章