LeetCode周赛328，官方练习场
LeetCode周赛328，官方练习场
作者 | 梁唐
出品 | 公众号：Coder梁（ID：Coder_LT）
大家好，我是梁唐。
今天是周一，我们照惯例来看看昨天的LeetCode周赛。
这次是LeetCode周赛第328场，这一次同样是官方的福利场。所有通过一题的同学都可以获得官方的学习专属福利。
这场的赛题难度不低，尤其对于初学者而言，可能从第二题开始就会开始很棘手。不少同学也在评论区里吐槽了难度，但不考虑比赛，仅考虑对算法能力的锻炼程度来看的话，那还是很值得一做的。
数组元素和与数字和的绝对差
给你一个正整数数组 nums 。
- 元素和 是
nums中的所有元素相加求和。 - 数字和 是
nums中每一个元素的每一数位（重复数位需多次求和）相加求和。
返回 元素和 与 数字和 的绝对差。
注意：两个整数 x 和 y 的绝对差定义为 |x - y| 。
题解
签到题，这里我懒得将数字按位拆分了。直接使用Python将数字转化成字符串，再对字符串进行求和。
class Solution:
def differenceOfSum(self, nums: List[int]) -> int:
s1 = sum(nums)
s2 = 0
for n in nums:
st = str(n)
for s in st:
s2 += ord(s) - ord('0')
return abs(s1 - s2)
子矩阵元素加 1
给你一个正整数 n ，表示最初有一个 n x n 、下标从 0 开始的整数矩阵 mat ，矩阵中填满了 0 。
另给你一个二维整数数组 query 。针对每个查询 query[i] = [row1i, col1i, row2i, col2i] ，请你执行下述操作：
- 找出 左上角 为
(row1i, col1i)且 右下角 为(row2i, col2i)的子矩阵，将子矩阵中的 每个元素 加1。也就是给所有满足row1i <= x <= row2i和col1i <= y <= col2i的mat[x][y]加1。
返回执行完所有操作后得到的矩阵 mat 。
题解
这道题拿到手看了一下数据规模稍微计算了一下就能发现直接暴力会超时。
接着我的第二反应就是二维树状数组的模板题，但转念一想，这只是周赛的第二题，显然不应该出现二维树状数组这样的解法。这里我要吐槽一下，虽然可以不使用二维树状数组搞定。但和使用基本上没差，因为不了解二维树状数组的同学也很难想到正解。
正解是使用二维差分数组，所谓二维差分数组可以理解成二维前缀和。
为了方便大家理解，我们先来考虑一维的情况。假设本题是一维的，给定我们一系列区间，将区间内的元素增加1。进行若干次操作之后，要求最终的数组。这题相信大家都很容易想到，我们可以使用一个数组记录差分。比如我们要将[l,r]区间数值加一。
我们当然可以使用遍历去执行，但这显然非常耗时。所以我们要引入差分数组，假设差分数组叫做diff。我们将diff[l]+1，表示从l位置开始，右侧的值全部增加1，直到r结束，所以我们还要将diff[r+1]-1。对于最终的答案 ret[i] 等于 diff 数组0到i 之和。
二维差分也是同样的操作，只不过将一维换成了二维而已。对于(r1, c1)到(r2, c2)区间全部增加1，我们使用差分数组时，需要进行四步操作，前三步分别是diff[r1][c1]+1, diff[r1][c2+1]-1, diff[r2+1][c1]-1。这三步比较好理解，第四步还需要将diff[r2+1][c2+1]+1。
因为(r2+1, c2+1)及右下角的位置同时被diff[r1][c2+1]-1, diff[r2+1][c1]-1覆盖了两次，所以要再加回来。
直接写二维差分可能会比较棘手，可以先从一维开始理解会容易一些。
class Solution {
public:
vector<vector<int>> rangeAddQueries(int n, vector<vector<int>>& queries) {
vector<vector<int>> diff(n+2, vector<int>(n+2, 0));
for (auto &q: queries) {
int r1 = q[0], c1 = q[1], r2 = q[2], c2 = q[3];
diff[r1][c1]++; diff[r2+1][c2+1]++;
diff[r1][c2+1]--; diff[r2+1][c1]--;
}
vector<vector<int>> ret(n, vector<int>(n, 0));
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) ret[i][j] = diff[i][j];
// 先累加行，再累加列
for (int i = 0; i < n; i++) for (int j = 1; j < n; j++) ret[i][j] += ret[i][j - 1];
for (int i = 1; i < n; i++) for (int j = 0; j < n; j++) ret[i][j] += ret[i - 1][j];
return ret;
}
};
统计好子数组的数目
给你一个整数数组 nums 和一个整数 k ，请你返回 nums 中 好 子数组的数目。
一个子数组 arr 如果有 至少 k 对下标 (i, j) 满足 i < j 且 arr[i] == arr[j] ，那么称它是一个 好 子数组。
子数组 是原数组中一段连续 非空 的元素序列。
题解
解题的关键在于子数组而不是子序列，子数组需要元素连续。我们可以枚举子数组的右侧边界r，如果我们可以找到满足k的限制的最大左侧边界l。那么对于l左侧的位置都可以构成答案的左端点，此时贡献的答案种数为l+1。
推理到这里，不难发现这是双指针的套路。我们枚举右侧边界r，随着r的增大，区间内的元素在增加。当满足是好的子数组时移动左侧边界l，找到l的极限位置。之后，答案加上l+1。
剩下的问题是如何判断子数组是否是好的，其实非常简单。当区间内增加一个新的元素时，它只能和区间内同样的元素配对。区间内有几个值相同的元素，就能增加几个配对。所以我们只需要维护一下区间内各个元素的数量即可。
class Solution {
public:
long long countGood(vector<int>& nums, int k) {
long long ret = 0;
int l = 0;
int n = nums.size();
map<int, int> mp;
long long tmp = 0;
for (int r = 0; r < n; r++) {
// 配对数加上区间内元素的个数
tmp += mp[nums[r]];
mp[nums[r]]++;
// 移动l之后，会减少区间内nums[l]个数-1的配对数，因此判断条件为tmp - (mp[nums[l]] - 1)
while (l < r && tmp - mp[nums[l]] + 1 >= k) {
tmp -= mp[nums[l]] - 1;
mp[nums[l++]]--;
}
if (tmp >= k)
ret += l+1;
}
return ret;
}
};
最大价值和与最小价值和的差值
给你一个 n 个节点的无向无根图，节点编号为 0 到 n - 1 。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间有一条边。
每个节点都有一个价值。给你一个整数数组 price ，其中 price[i] 是第 i 个节点的价值。
一条路径的 价值和 是这条路径上所有节点的价值之和。
你可以选择树中任意一个节点作为根节点 root 。选择 root 为根的 开销 是以 root 为起点的所有路径中，价值和 最大的一条路径与最小的一条路径的差值。
请你返回所有节点作为根节点的选择中，最大 的 开销 为多少。
题解
由每个节点的值都为正数，很容易发现所谓最大路径减去最小路径，即为最大路径减去较小的一个端点。
剩下的问题就是怎么求这个最大的路径，因为树中的节点数是1e5，显然我们不能枚举每一个节点作为根节点。针对这个问题，如果大家对于树结构比较熟悉的话，其实可以发现不论当前的根节点是谁，答案的可能性都只有两种。
假设当前根节点是r，分别是：
- 包含
r的路径 r子树中的路径（不包含r)
这两种情况看起来好像不太好直接求，但我们可以简单转化一下。转化成：
- 以
r开头，完整的路径和 - 以
r开头，去掉一个端点的路径和
如果r包含多个子树，我们可以选择一个完整路径和与去掉一个端点的路径和进行拼接。对于r子树中的情况，我们一样可以在递归时覆盖到。
也就是说不同规模的问题，拆分之后的结果构成是类似的。那么很明显，我们可以使用递归来搞定。在本题当中还不只是简单的递归问题，当我们求解当前问题时，我们需要先求出子问题。当前问题可以通过子问题转移得到，这也符合动态规划中的状态转移。
所以这既是递归问题，也是动态规划问题。一般来说我们把这样的问题叫做树形dp。
我们让递归函数返回一个pair，pair的第一个元素是包含了树根的最大路径，第二个元素是不包含树根的最大路径。更多细节参考代码注释。
这题的状态相对不是那么明显，不小心很容易搞乱。大家做题的时候不妨在纸上多画几种情况，列举一下从而更方便理解。
class Solution {
public:
long long maxOutput(int n, vector<vector<int>>& edges, vector<int>& price) {
vector<int> graph[n+2];
// 建图
for (auto &vt: edges) {
int u = vt[0], v = vt[1];
graph[u].push_back(v);
graph[v].push_back(u);
}
long long ret = 0;
function<pair<long long, long long>(int, int)> dfs = [&](int u, int f) {
// fst为子树中包含u的最大路径，sed为不包含叶子的最大路径
long long fst = price[u], sed = 0;
for (auto v: graph[u]) {
if (v == f) continue;
auto cur = dfs(v, u);
long long fs = cur.first, se = cur.second;
// se + fst 为 子树v中不包含叶子的最大路径+其他子树包含叶子的值
// fs + sed 为 子树v包含叶子+其他子树不包含叶子
ret = max({ret, se + fst, fs + sed});
// 子树v包含叶子连上节点u
fst = max(fst, fs + price[u]);
// 子树v不包含叶子连上节点u
sed = max(sed, se + price[u]);
}
return make_pair(fst, sed);
};
dfs(0, -1);
return ret;
}
};