LeetCode周赛292，800多人做出第四题，大佬怒喷太简单……
大家好，我是梁唐。本文始发于公众号：Coder梁
今天照惯例，我们来聊聊昨天的LeetCode周赛。
这次的比赛是Cider赞助的，居然只有前50名能拿到简历内推……emmm，我感觉这些公司有些脱离群众……也不看看能进前50的都是什么神仙……
这次的题目我个人感觉还是不错的，虽然我也没有做得很顺。但没想到赛后看了一眼评论区，居然看到有大佬在线怒喷题目太简单了，成了手速场……
显然，这样凡尔赛的言论点燃了一堆人的怒火……连带着我这个前竞赛选手看到了也非常不适。毕竟我差点没能做出第四题……
好了，吐槽完毕，我们来看题吧。
吐槽和抱怨是不能变强的，只有踏踏实实地思考、练习再思考再练习才可以……
字符串中最大的 3 位相同数字
给你一个字符串 num ，表示一个大整数。如果一个整数满足下述所有条件，则认为该整数是一个 优质整数 ：
- 该整数是 num 的一个长度为 3 的 子字符串 。
- 该整数由唯一一个数字重复 3 次组成。
以字符串形式返回 最大的优质整数 。如果不存在满足要求的整数，则返回一个空字符串 "" 。
注意：
- 子字符串 是字符串中的一个连续字符序列。
- num 或优质整数中可能存在 前导零 。
题解
emmm，我承认，第一题的确是读完题目应该都能写的那种。毕竟确实很简单。
一看到这种涉及到字符串操作的问题，我本能地就选择了Python。毕竟Python里面字符串的api比较多，写起来有各种fancy的技巧。
在这道题当中，可以直接使用切片来判断三个字符是否一样。
class Solution:
def largestGoodInteger(self, num: str) -> str:
st = set([str(i) * 3 for i in range(10)])
n = len(num)
ret = ''
for i in range(0, n-2):
sub = num[i: i+3]
if sub in st:
if ret == '' or sub > ret:
ret = sub
return ret
当然用C++也不复杂，老老实实地判断连续三个字符是否相等即可。
class Solution {
public:
string largestGoodInteger(string num) {
string ret = "";
int n = num.length();
for (int i = 2; i < n; i++) {
if (num[i] == num[i-1] && num[i-1] == num[i-2]) {
ret = max(ret, num.substr(i-2, 3));
}
}
return ret;
}
};
统计值等于子树平均值的节点数
给你一棵二叉树的根节点 root ，找出并返回满足要求的节点数，要求节点的值等于其 子树 中值的 平均值 。
注意：
- n 个元素的平均值可以由 n 个元素 求和 然后再除以 n ，并 向下舍入 到最近的整数。
- root 的 子树 由 root 和它的所有后代组成。
题解
由于我们要枚举每一个点，判断它是否等于它子树的平均值，我们当然可以不停地枚举，但显然这样会非常耗时。
最好的办法，就是利用递归的性质，从下往上地遍历树中的节点。并且对于某一个点而言，不再是计算以它为子树的均值，而是总和以及数量。这样在向上回溯的过程当中，这些结果可以重复使用。
比如第一个样例当中，我们通过递归算出了8这个子树的总和是9，节点数量是3。在我们计算根是4的这棵树的时候，我们就可以直接将8的结果和5的结果相加。利用这个性质，我们在计算4的均值的时候，就没必要再遍历一次8或者5了。
所以我们的递归函数需要同时返回总和以及节点数量，当时没多想，直接用了Python：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def averageOfSubtree(self, root: Optional[TreeNode]) -> int:
ret = 0
def dfs(u):
nonlocal ret
tot, cnt = u.val, 1
if u.left is not None:
lt, lc = dfs(u.left)
tot += lt
cnt += lc
if u.right is not None:
rt, rc = dfs(u.right)
tot += rt
cnt += rc
if tot // cnt == u.val:
ret += 1
return tot, cnt
dfs(root)
return ret
附上C++版本：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int averageOfSubtree(TreeNode* root) {
int ret = 0;
function<pair<int, int>(TreeNode*)> f = [&](TreeNode* u) {
int tot = u->val, cnt = 1;
if (u->left != nullptr) {
pair<int, int> cur = f(u->left);
tot += cur.first, cnt += cur.second;
}
if (u->right != nullptr) {
pair<int, int> cur = f(u->right);
tot += cur.first, cnt += cur.second;
}
if (tot / cnt == u->val) ret++;
return make_pair(tot, cnt);
};
f(root);
return ret;
}
};
这段代码的逻辑和上面Python是一样的，不过这里用了匿名函数。
在C++中使用匿名函数递归的时候需要注意，不能使用auto来为匿名函数推导类型，必须要手动书写。
统计打字方案数
Alice 在给 Bob 用手机打字。数字到字母的 对应 如下图所示。
为了 打出 一个字母，Alice 需要 按 对应字母 i 次，i 是该字母在这个按键上所处的位置。
- 比方说，为了按出字母 's' ，Alice 需要按 '7' 四次。类似的， Alice 需要按 '5' 两次得到字母 'k' 。
- 注意，数字 '0' 和 '1' 不映射到任何字母，所以 Alice 不 使用它们。
但是，由于传输的错误，Bob 没有收到 Alice 打字的字母信息，反而收到了 按键的字符串信息 。
- 比方说，Alice 发出的信息为 "bob" ，Bob 将收到字符串 "2266622" 。
给你一个字符串 pressedKeys ，表示 Bob 收到的字符串，请你返回 Alice 总共可能发出多少种文字信息 。
由于答案可能很大，将它对 109 + 7 取余 后返回。
题解
我们可以注意到7和9两个位置有4个字母，其他位置只有3个字母。
接着我们可以想到，同样一个数字，只有连续按才有多种可能。所以我们要做的就是把字符串按照连续的字符做切分，分成若干段连续的字符。然后针对每一段分别计算不同字母组合的数量，最后把每一段的数量相乘就是答案。
我们进一步可以抽象成若干个f(n, m)相乘的问题，这里的n是连续字符的数量，m是按键的字母数量。m只有两种取值3或4。
那f(n, m)怎么求呢？
直接求似乎是比较困难的，毕竟可能性太多，我们可以考虑最后一个字母。当n > m时，最后一个字母有m种可能。比如以数字2为例，我们可以只用一个2获取a，也可以用两个2获取b，还可以用3个2获取c。如果我们最后一个字符是a，一共有f(n-1, m)种可能，因为n个2，用掉了一个，还剩n-1个。如果最后一个字符是b，那么有f(n-2, m)种可能，同理c对应的可能是f(n-3, m)，那么f(n, m)就是这三个值之和。
我们可以发现这当中存在递推关系，我们已经知道了字符串的最大长度是1e5，所以我们可以事先把所有的f(n, 3)和f(n, 4)都计算出来，之后直接查表即可。
class Solution {
public:
long long MOD = 1e9 + 7;
long long dp[2][100050];
int countTexts(string press) {
int n = press.length();
// dp[0][] 存储3个字符的情况
// dp[1][] 存储4个字符的情况
dp[0][0] = 1;
dp[1][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= min(i, 3); j++) {
dp[0][i] += dp[0][i-j];
dp[0][i] %= MOD;
}
for (int j = 1; j <= min(i, 4); j++) {
dp[1][i] += dp[1][i-j];
dp[1][i] %= MOD;
}
}
char last = press[0];
int l = 1;
long long ret = 1;
for (int i = 1; i < n; i++) {
// 统计连续的字符数量，查表即可
if (press[i] == last) l++;
else {
int m = 3 + (last == '7' || last == '9');
ret *= dp[m-3][l];
ret %= MOD;
l = 1;
last = press[i];
}
}
int m = 3 + (last == '7' || last == '9');
ret *= dp[m-3][l];
ret %= MOD;
return ret;
}
};
检查是否有合法括号字符串路径
一个括号字符串是一个 非空 且只包含 '(' 和 ')' 的字符串。如果下面 任意 条件为 真 ，那么这个括号字符串就是 合法的 。
- 字符串是 () 。
- 字符串可以表示为 AB（A 连接 B），A 和 B 都是合法括号序列。
- 字符串可以表示为 (A) ，其中 A 是合法括号序列。
给你一个 m x n 的括号网格图矩阵 grid 。网格图中一个 合法括号路径 是满足以下所有条件的一条路径：
- 路径开始于左上角格子 (0, 0) 。
- 路径结束于右下角格子 (m - 1, n - 1) 。
- 路径每次只会向 下 或者向 右 移动。
- 路径经过的格子组成的括号字符串是 合法 的。
如果网格图中存在一条 合法括号路径 ，请返回 true ，否则返回 false 。
题解
这题很有意思，比赛的时候看到数据范围很小，棋盘只有100 x 100，加上当时也没有想到更好的方法吗，决定用宽度优先搜索试一下。
宽搜的方法很简单，枚举从(0, 0)位置出发的所有路径中途的左右括号的数量。众所周知在一个连续的括号内部，当从左往右遍历时如果遇到的右括号的数量大于左括号，那么就说明一定不是合法匹配。
所以我们可以搜索的时候去掉这些中间结果，但很遗憾，这样的做法超时了。
我又加上了使用set进行中间状态去重的逻辑，依然还是超时。一直到比赛之前，突然想到了一个优化方法。对于一个合法的路径而言，它的路径长度是确定的。那么对应的左右括号的数量也是确定的，这个是可以直接算出来的。
既然最后的数量确定，那么就说明了在路径的中间结果当中它的左右括号的数量都不可能超过这个值。因此，除了左括号数量不能小于右括号之外，还可以加上一条它的数量必须要小于这个限制，否则一样不成立。
加上了这个剪枝之后终于通过了。
class Solution {
public:
struct P {
int x, y, lef, rig;
P(){}
P(int _x, int _y, int l, int r): x{_x}, y{_y}, lef{l}, rig{r} {}
// 友元函数添加比较运算符
friend bool operator < (const P& na, const P& nb) {
if (na.x == nb.x && na.y == nb.y) {
return na.lef == nb.lef ? na.rig < nb.rig : na.lef < nb.lef;
}
return na.x == nb.x ? na.y < nb.y : na.x < nb.x;
}
};
bool hasValidPath(vector<vector<char>>& grid) {
queue<P> que;
int n = grid.size(), m = grid[0].size();
// 开头是右括号，结尾是左括号或者路径长度是奇数，直接return false
if (grid[0][0] == ')') return false;
if (grid[n-1][m-1] == '(') return false;
if ((n + m) % 2 == 0) return false;
que.push(P(0, 0, 1, 0));
int fx[2][2] = {{0, 1}, {1, 0}};
// 左括号和右括号数量
int cnt = (n + m - 1) / 2;
bool flag = false;
set<P> st;
while (!que.empty()) {
P u = que.front();
// 如果已经抵达终点，且完美匹配，返回true
if (u.x == n-1 && u.y == m-1 && u.lef == u.rig) return true;
que.pop();
for (int i = 0; i < 2; i++) {
int nx = u.x + fx[i][0], ny = u.y + fx[i][1];
if (ny < m && nx < n) {
int lef = u.lef;
int rig = u.rig;
if (grid[nx][ny] == '(') lef++;
else rig++;
// 如果左括号数量超过限制或者是小于右括号数量，说明不可能合法
if (lef >= rig && lef <= cnt) {
P next = P(nx, ny, lef, rig);
if (!st.count(next)) {
que.push(next);
st.insert(next);
}
}
}
}
}
return flag;
}
};
比赛的时候隐隐感觉这种做法并不是正解，但又想不出还有什么方法。赛后看了大佬的题解才恍然大悟，其实这题还可以使用动态规划来解决。
考虑dp[i][j][k]，这里的i，j显然表示坐标（i，j）。这里的k表示从（0，0）到（i，j）的路径当中，左括号数量和右括号数量的差值。dp[i][j][k]是bool类型，表示是否有这样的路径。
对于dp[i][j][k]来说，我们只需要考虑它左侧和上侧的位置即可，基本上把dp数组的表示想清楚了，整个动态规划还是挺好想的。
class Solution {
public:
bool hasValidPath(vector<vector<char>>& grid) {
int n = grid.size(), m = grid[0].size();
if (grid[0][0] == ')') return false;
if (grid[n-1][m-1] == '(') return false;
if ((n + m) % 2 == 0) return false;
int cnt = (n + m - 1) / 2;
vector<vector<vector<bool>>> dp(n+2, vector<vector<bool>>(m+2, vector<bool>(cnt+2, false)));
dp[0][0][1] = true;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int b = grid[i][j] == '(' ? 1 : -1;
for (int k = 0; k <= cnt; k++) {
int kk = k - b;
if (kk < 0 || kk > cnt) continue;
if (i) dp[i][j][k] = dp[i][j][k] | dp[i-1][j][kk];
if (j) dp[i][j][k] = dp[i][j][k] | dp[i][j-1][kk];
}
}
}
return dp[n-1][m-1][0];
}
};
和搜索的方法相比，显然动态规划的代码更加清晰和优雅。
老实说之前的确很少做过这种类型的动态规划，也难怪比赛的时候想不出来。不管怎么说，这一次算是学到了，至少对我来说，这一次的比赛题目很不错，让我get了新的思路。
其实难度大不大并不重要，毕竟难度这个东西并不是普世的，能够学到东西才是王道。
好了，关于这次的比赛就先聊到这里，感谢大家的阅读。
转载自:https://juejin.cn/post/7095618253238009863