leetcode 第 292 场算法比赛

零、背景

这次比赛题目不难，但是我打字速度太慢，没进前一百名。

我计划再次启动练习打字的计划了，速度提上来后，排名应该可以提升不少。

一、字符串中最大的 3 位相同数字

题意：给一个字符串，求最大的连续三个相同数字子串。

思路：循环一遍找到所有子串答案，求最大值即可。

二、统计值等于子树平均值的节点数

题意：给一个二叉树，问子树的平均值等于子树根的值的个数。
子树的平均值定义：子树所有节点之和除以子树节点个数，向下取整。

思路：递归求出每个子树的节点和与节点个数，就可以判断当前子树是不是答案。
子树的返回值是子树的节点和与节点个数，这样就可以求出父节点作为子树的答案。

三、统计打字方案数

题意：给一个老式按键手机，不同数字映射若干不同的字母。
如果一个数字映射多个字母，按出对应字母需要按键多次，次数就是字母的位置。
例如，数字 2 对应 abc 三个字母，敲出字母 a 需要按一次数字 2，敲出字母 c 需要按 3 次数字 2。
现在给一个数字字符串，代表按键顺序，问可以敲出多少不同的字符串。

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

状态定义：f(n) 代表前 n 个数字可以按出的字符串个数。

根据最后一位连续数字的长度，以及这个数字最多可以按多少次，分别枚举按的次数。

状态转移方程：

f(n)=f(n-1) + f(n-2) + ... + f(n-k)

含义：最后一个数字连续的长度至少为 k，且这个数字映射的字母个数至少为 k 个。

四、检查是否有合法括号字符串路径

题意：给一个矩阵，值是左括号或者右括号。
问从左上角到右下角的路径中是否存在一条合法的括号匹配。

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

判断一个字符串是否括号匹配时，需要使用栈来判断。
实际上，可以不使用栈，计数左括号的个数即可。
从左到右扫描字符串，遇到左括号加一，遇到右括号减一，中间没有得到负值且最终结果为 0 代表括号匹配。

作为，对于这道题，每个状态就是左括号的个数集合。

状态定义：f(i, j) 到达这个坐标时，不同左括号个数集合，空代表不可到达。

状态转移：左边和上边的状态合并，当前坐标值是左括号，则集合里的值都加1，否则都减一。

答案：判断最后一个状态的集合里是否存在 0。

五、最后

这次比赛题目不难。

加油，算法人。

《完》

-EOF-

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