leetcode 第 289 场算法比赛

零、背景

这次比赛题目不难，第三题看错题了，浪费不少时间。

最后理解正确题意后，双层循环敲错一个地方，导致错了一次，最终没能进去前百名，遗憾。

下面来看看题解吧。

一、计算字符串的数字和

题意：给一个数字字符串。
从前到后 k 个一组，每组内的数字字符相加得到新的数字，最后所有数字组成新的字符串。
如果新的字符串长度大于 K，继续进行上面的操作，直到不大于 K。
求最终的字符串。

思路：按照题意模拟即可。

通过时间：0:05:13

二、完成所有任务需要的最少轮数

题意：给一个数组，每轮可以消除两个或三个相同的数字，问最少需要多少轮可以消除所有数字。
如果存在数字无法消除，返回 -1。

思路：先使用 map 统计数字，每个数字单独判断需要多少轮。

每个数字单独处理逻辑如下：

1）如果数字出现一次，无法消除，没有答案。

2）如果数字大于一次，优先使用三个数字一轮来消除，根据剩余的数字来分情况判断。

-）剩余 0 个数字，则所有数字都使用 三个数字消除。
-）剩余 1 个数字，需要取消一轮三个数字，组成两轮 2 个数字。
-）剩余 2 个数字，则增加一轮 2 个数字即可。

通过时间： 0:10:06

三、转角路径的乘积中最多能有几个尾随零

题意：给一个矩阵，求一个不重叠的路径，这个路径最多只能有一个拐角。
问路径上数字乘积最多有多少个后缀 0。

思路：

看错题了，以为可以有无数个拐角，发现搜索爆炸，状态无法保存，先做第四题。

第四题过之后，看榜单第三题过的人很多，于是怀疑看错题了。
再阅读题，发现只能有一个拐角，那就是大水题，枚举所有拐角即可。

由于求的是乘积后缀 0 最多，所以对于一个拐角路径，两头无限扩充到边缘，答案只会更优。
同样道理，对于一个没有拐角的直线路径，加一个拐角，答案也只会更优。

所以最优答案肯定是一个拐角，两头是与边缘接触。
注：1*n 的矩阵，可以理解为拐角一头长度为 0 即可。

算法：

首先预处理所有点在四个方向到达边缘时，乘积上 2 的个数与 5 的个数。
然后枚举每个顶点为拐角，再枚四个方向两两组合为拐角时，能够得到的最优答案。

注：统计完 2 和 5 后，答案为最少的那个。

通过时间；0:43:13
罚时：错误一题，罚时 5 分钟。

四、相邻字符不同的最长路径

题意：给一个树，每个节点有一个字母。
求一个最长路径，路径上的相邻两个节点字母不同。

思路：简单题，一个递归解决。

递归的时候，求出子树上的最长路径，更新答案。
递归的返回值为以子树为端点的最长路径。

子树最长路径：子树根自身长度为1，再找到 节点值与自己不同的路径最长的儿子。

子树答案：自己长度为 1， 再加上 节点值与自己不同的路径最长的两个儿子。

通过时间：0:24:15

五、最后

这次比赛看错题了，不然有可能进入前百名。

另外，这次比赛笔误错误一次，不然也可以进去前百名。

但是再一想，也许快进去前百名的这些人都是我这样想的。

从这个角度看，还是自己的问题。

以后还是要认真读题，并加强阅读速度、理解速度、思考速度，敲代码速度的能力。

加油，算法人。

《完》

-EOF-

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