LeetCode周赛289，太考验手速，我落败了……
LeetCode周赛289，太考验手速，我落败了……
作者 | 梁唐
出品 | 公众号：Coder梁（ID：Coder_LT）
大家好，日拱一卒，我是梁唐。
今天是周一，老规矩，我们来一起看下LeetCode周赛第289场。
这一场比赛的赞助商是海康威视，前20名有礼物，没有内推机会。
这一场的难度不算大，比较考验手速。即使AK也需要很高的手速，才能拿到好的名次……
我在比赛结束前20分钟结束，也只有300多名……
好了，废话不多说，我们一起来看题吧。
计算字符串的数字和
给你一个由若干数字（0 - 9）组成的字符串 s ，和一个整数。
如果 s 的长度大于 k ，则可以执行一轮操作。在一轮操作中，需要完成以下工作：
- 将 s 拆分 成长度为 k 的若干 连续数字组 ，使得前 k 个字符都分在第一组，接下来的 k 个字符都分在第二组，依此类推。注意，最后一个数字组的长度可以小于 k 。
- 用表示每个数字组中所有数字之和的字符串来 替换 对应的数字组。例如，"346" 会替换为 "13" ，因为 3 + 4 + 6 = 13 。
- 合并 所有组以形成一个新字符串。如果新字符串的长度大于 k 则重复第一步。
返回在完成所有轮操作后的 s 。
解答
水题，K个数字一组求和之后再转成string。循环以上过程，直到长度小于K
class Solution {
public:
string digitSum(string s, int k) {
while (s.length() > k) {
int n = s.length();
string next = "";
for (int i = 0; i < n; i += k) {
int tot = 0;
for (int j = i; j < min(i+k, n); j++) {
tot += s[j] - '0';
}
next += to_string(tot);
}
s = next;
}
return s;
}
};
完成所有任务需要的最少轮数
给你一个下标从 0 开始的整数数组 tasks ，其中 tasks[i] 表示任务的难度级别。在每一轮中，你可以完成 2 个或者 3 个 相同难度级别 的任务。
返回完成所有任务需要的 最少 轮数，如果无法完成所有任务，返回 -1 。
解答
很容易想到，我们可以统计每个数字出现的次数。
显然，当出现次数大于1时一定可以拆分成若干个2和3的和。我们也可以简单证明一下，任何自然数对3取模只有3种可能：0、1、2。
如果余数为0，那么很简单，我们3个一组拆分即可。如果余数为1，我们可以先拆分出两个2，由于4 % 3 = 1，减去4之后必然可以被3整除，所以剩下的部分按3拆分即可。如果余数为2，那么可以先拆分出一个2，剩下的再对3拆分。
按照3拆分的轮数一定比按2拆分更优，得解
class Solution {
public:
int minimumRounds(vector<int>& tasks) {
map<int, int> mp;
int n = tasks.size();
for (int i = 0; i < n; i++) {
mp[tasks[i]]++;
}
int ret = 0;
for (auto it = mp.begin(); it != mp.end(); it++) {
int k = it->first, v = it->second;
if (v == 1) return -1;
if (v % 3 == 0) {
ret += v / 3;
}else if (v % 3 == 1) {
ret += (2 + (v - 4) / 3);
}else {
ret += (1 + (v - 2) / 3);
}
}
return ret;
}
};
转角路径的乘积中最多能有几个尾随零
给你一个二维整数数组 grid ，大小为 m x n，其中每个单元格都含一个正整数。
转角路径 定义为：包含至多一个弯的一组相邻单元。具体而言，路径应该完全 向水平方向 或者 向竖直方向 移动过弯（如果存在弯），而不能访问之前访问过的单元格。在过弯之后，路径应当完全朝 另一个 方向行进：如果之前是向水平方向，那么就应该变为向竖直方向；反之亦然。当然，同样不能访问之前已经访问过的单元格。
一条路径的 乘积 定义为：路径上所有值的乘积。
请你从 grid 中找出一条乘积中尾随零数目最多的转角路径，并返回该路径中尾随零的数目。
注意：
- 水平 移动是指向左或右移动。
- 竖直 移动是指向上或下移动。
解答
首先可以注意到数据范围，虽然看起来n和m的范围很大，最大有1e5。但往下看可以看到又说了m * x <= 1e5，这相当于是说格子的数量最大不会超过1e5。
其次虽然看起来选择一个拐角有些吓人，但稍微深入想一下会发现，其实只要确定拐角点，而不需要关注拐角的起始位置。
比如下图当中，我们确定了某一个位置(i, j)。从这个点出发可以连出上下左右四条路径。在上下和左右当中任意各自选出一条，就可以组成一个拐角。对于每一个拐角来说，一定是连到边缘是最优的。
因为我们的目的是找到一个拐角，它当中所有数相乘之后的末尾0最多。由于是乘法操作，并且每一个元素都不为0，所以多乘几个数并不会使得末尾的0减少。所以我们只需要考虑连到边界的情况就行了。
乘积末尾有几个0怎么求呢？
其实很简单，我们可以利用简单的数论知识。10分解质因数是2和5，并且每一个自然数分解质因数的结果唯一。所以我们只需要考虑这一系列数中因数2和因数5的数量，少的那个就是0的数量。比如25 * 2，虽然可以分解出两个因数5，但是因数2只有1个，所以结果就只有一个0。如果是25 * 4，由于因数2多了一个，所以结果有两个0。
所以我们可以计算出每一个方向上的2和5的数量，由于会涉及多个区间和的计算， 所以我们可以使用前缀和的思想。
这里我是分成了上下左右四个方向分别计算了2和5的因数数量，其实只算两个方向，另外两个方向可以通过作差的方式得到。
然后我们枚举一下拐角的可能性，找到其中的最大解即可。
class Solution {
public:
int fac_cnt(int n, int f) {
int ret = 0;
while (n % f == 0) {
ret ++;
n /= f;
}
return ret;
}
int maxTrailingZeros(vector<vector<int>>& grid) {
vector<int> two_cnt(1002, 0), fv_cnt(1002, 0);
// 初始化，由于grid[i][j] 在1000以内，可以先初始化好1000以内每个数2和5的因数个数
for (int i = 1; i <= 1000; i++) {
two_cnt[i] = fac_cnt(i, 2);
fv_cnt[i] = fac_cnt(i, 5);
}
int n = grid.size(), m = grid[0].size();
// 使用pair分别存储2和5的数量
pair<int, int> hoz_lef[n+2][m+2], hoz_rig[n+2][m+2], vet_up[n+2][m+2], vet_dn[n+2][m+2];
memset(hoz_lef, 0, sizeof hoz_lef);
memset(hoz_rig, 0, sizeof hoz_rig);
memset(vet_up, 0, sizeof vet_up);
memset(vet_dn, 0, sizeof vet_dn);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int v = grid[i][j];
int two = two_cnt[v], five = fv_cnt[v];
vet_dn[i][j] = make_pair(two + (i == 0 ? 0 : vet_dn[i-1][j].first), five + (i == 0 ? 0: vet_dn[i-1][j].second));
hoz_lef[i][j] = make_pair(two + (j == 0 ? 0 : hoz_lef[i][j-1].first), five + (j == 0 ? 0: hoz_lef[i][j-1].second));
}
for (int j = m-1; j > -1; j--) {
int v = grid[i][j];
int two = two_cnt[v], five = fv_cnt[v];
hoz_rig[i][j] = make_pair(two + (j == (m-1) ? 0: hoz_rig[i][j+1].first), five + (j == (m-1)? 0: hoz_rig[i][j+1].second));
}
}
for (int i = n-1; i > -1; i--) {
for (int j = 0; j < m; j++) {
int v = grid[i][j];
int two = two_cnt[v], five = fv_cnt[v];
vet_up[i][j] = make_pair(two + (i == (n-1) ? 0: vet_up[i+1][j].first), five + (i == (n-1) ? 0: vet_up[i+1][j].second));
}
}
int ret = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int v = grid[i][j];
// 拐角一共有4种情况，分别枚举
// v重复计算了，所以要去除
auto c1 = make_pair(hoz_lef[i][j].first + vet_up[i][j].first, hoz_lef[i][j].second + vet_up[i][j].second);
auto c2 = make_pair(hoz_lef[i][j].first + vet_dn[i][j].first, hoz_lef[i][j].second + vet_dn[i][j].second);
auto c3 = make_pair(hoz_rig[i][j].first + vet_up[i][j].first, hoz_rig[i][j].second + vet_up[i][j].second);
auto c4 = make_pair(hoz_rig[i][j].first + vet_dn[i][j].first, hoz_rig[i][j].second + vet_dn[i][j].second);
int cur = min(c1.first - two_cnt[v], c1.second - fv_cnt[v]);
ret = max(cur, ret);
cur = min(c2.first - two_cnt[v], c2.second - fv_cnt[v]);
ret = max(cur, ret);
cur = min(c3.first - two_cnt[v], c3.second - fv_cnt[v]);
ret = max(cur, ret);
cur = min(c4.first - two_cnt[v], c4.second - fv_cnt[v]);
ret = max(cur, ret);
}
}
return ret;
}
};
解法当中藏了一个小trick，就是拐角拐弯的点，在两次求和当中都被包含了，因此要去掉。
比如上图，我们在计算拐角中元素因数2和5的数量时，拐角1处的数量在竖直和水平当中各自被计算了一次，因此需要减去重复。
相邻字符不同的最长路径
给你一棵 树（即一个连通、无向、无环图），根节点是节点 0 ，这棵树由编号从 0 到 n - 1 的 n 个节点组成。用下标从 0 开始、长度为 n 的数组 parent 来表示这棵树，其中 parent[i] 是节点 i 的父节点，由于节点 0 是根节点，所以 parent[0] == -1 。
另给你一个字符串 s ，长度也是 n ，其中 s[i] 表示分配给节点 i 的字符。
请你找出路径上任意一对相邻节点都没有分配到相同字符的 最长路径 ，并返回该路径的长度。
解答
这是一道经典的树上求最长链路的问题。
对于树上的链路，分为两种，一种是从节点u到节点v，它们的深度依次递增。第二种是从节点v，到节点u，再到节点w。它们的深度是先减后增，呈倒V型。
题目给定的两个样例，刚好分别是这两种类型。
但还不至于此，我们进一步思考可以发现，本题的链路并没有和树根绑定。也就是说这样的通路可以不必经过根节点，这就带来了一个问题，如果不经过根节点，我们怎么枚举链路呢？
这需要用到一个分情况讨论的递归技巧，假设我们递归到了某个节点u，它对应原树中以u节点为根的子树。
经过u节点可能构成的答案有两种，对应上面的两种类型，一种是穿过u连向更上层的节点。还有一种是经过u本身的倒V型。
我们可以对这两种情况分情况讨论，首先对于第一种情况有一个限制，即u不能和u的父节点字符相同。如果满足条件我们返回什么呢？我们返回u的子节点当中的这种情况的最大值再加上u本身的长度1，假设递归函数dfs(u)返回的是以u为根节点的子树，单条路径能够达成的最长长度。
那么，我们可以写出递归式：
int dfs(int u) {
int ret = 0;
for (int v : edges[u]) {
ret = max(ret, dfs(v) + 1);
}
return ret;
}
我们再来看第二种情况，即穿过u的倒V型。这种情况不涉及u的父节点，所以我们可以不必考虑与父节点的冲突。这种倒V型的路径怎么求呢？其实观察一下就会发现，倒V型的路径其实就是u的两条子路径之和。要使得这两条子路径之和最大，那么显然我们应该从u的所有子路径当中选出两条最长的来。也就是说虽然看起来是两种情况，但是它们的递归结构是一样的。
在递归问题当中，通常我们只能针对一种情况进行递归构造。情况多了之后，不一定满足递归的传递性。这个时候不要慌张，不妨思考一下情况之间的关联，能否用一种情况去构造另外的情况。这是递归问题当中的常见技巧。
比赛的时候当中发现可能要考虑多种情况，所以使用了Python。因为Python的函数可以返回多个值，但其实没有必要。
class Solution:
def longestPath(self, parent: List[int], s: str) -> int:
mp = defaultdict(list)
for i, f in enumerate(parent):
mp[f].append(i)
ret = 1
def dfs(u, mk):
# 如果u是叶子结点，直接返回，不冲突返回1否则返回0
if len(mp[u]) == 0:
return 1 if s[u] != mk else 0
# 找出u节点两个子节点的最大长度
maxi1, maxi2 = 0, 0
for v in mp[u]:
cur = dfs(v, s[u])
if cur > maxi1:
maxi1, maxi2 = cur, maxi1
elif cur > maxi2:
maxi2 = cur
nonlocal ret
# 维护答案
ret = max(ret, maxi1 + maxi2 + 1)
# 如果和父节点冲突，返回0，否则返回maxi1 + 1
return maxi1 + 1 if s[u] != mk else 0
dfs(0, s[0])
return ret
赛后重新整理了C++版本，这里我本来是用匿名函数实现的。但担心有些同学可能对匿名函数不是很熟悉，因此也用常规的函数实现了一版，在注释当中。
class Solution {
public:
// int dfs(vector<vector<int>>& edges, string & s, int u, char mk, int &ret) {
// if (edges[u].size() == 0) {
// return s[u] != mk ? 1 : 0;
// }
// int maxi1 = 0, maxi2 = 0;
// for (auto v: edges[u]) {
// int cur = dfs(edges, s, v, s[u], ret);
// if (cur > maxi1) {
// maxi2 = maxi1;
// maxi1 = cur;
// }else if (cur > maxi2) {
// maxi2 = cur;
// }
// }
// ret = max(ret, maxi1 + maxi2 + 1);
// return s[u] != mk ? maxi1 + 1 : 0;
// }
int longestPath(vector<int>& parent, string s) {
int n = parent.size();
vector<vector<int>> edges(n+2);
for (int i = 0; i < n; i++) {
int v = parent[i];
if (v >= 0) {
edges[v].push_back(i);
}
}
int ret = 1;
auto f = [&](int u, char mk) -> int {
function<int(int, char)> func;
func = [&](int u, char mk) {
if (edges[u].size() == 0) {
return s[u] != mk ? 1 : 0;
}
int maxi1 = 0, maxi2 = 0;
for (auto v: edges[u]) {
int cur = func(v, s[u]);
if (cur > maxi1) {
maxi2 = maxi1;
maxi1 = cur;
}else if (cur > maxi2) {
maxi2 = cur;
}
}
ret = max(ret, maxi1 + maxi2 + 1);
return s[u] != mk ? maxi1 + 1 : 0;
};
return func(u, mk);
};
f(0, s[0]);
return ret;
}
};
这次比赛的题目难度不算非常高，但是梯度做得很好，难度逐渐增加，作为周赛还是非常不错的。
另外就是第三题的代码量很大，对于选手的编码和debug能力是一个很大的考验。我这一次就在第三题的调试上浪费了不少时间，短时间内狂敲一百多行还不能有错，确实不简单……
好了，关于这一次的比赛就说这么多，感谢大家的阅读。
喜欢本文的话不要忘记三连~
腾讯云开发者
