leetcode leetcode contest 328

双周赛的题目确实非常高，还是有许多题目自己不太会。

6291. 数组元素和与数字和的绝对差

元素和 是 nums 中的所有元素相加求和。
数字和 是 nums 中每一个元素的每一数位（重复数位需多次求和）相加求和。
返回 元素和 与 数字和 的绝对差。

注意：两个整数 x 和 y 的绝对差定义为 |x - y| 。

示例 1：

输入：nums = [1,15,6,3]
输出：9
解释：
nums 的元素和是 1 + 15 + 6 + 3 = 25 。
nums 的数字和是 1 + 1 + 5 + 6 + 3 = 16 。
元素和与数字和的绝对差是 |25 - 16| = 9 。

示例 2：

输入：nums = [1,2,3,4]
输出：0
解释：
nums 的元素和是 1 + 2 + 3 + 4 = 10 。
nums 的数字和是 1 + 2 + 3 + 4 = 10 。
元素和与数字和的绝对差是 |10 - 10| = 0 。

提示：

• 1 <= nums.length <= 2000
• 1 <= nums[i] <= 2000

地址

https://leetcode.cn/contest/weekly-contest-328/problems/difference-between-element-sum-and-digit-sum-of-an-array/

题意

直接遍历

思路

1. 直接求每一位数字的数字和即可，然后求数组中所有数字的和即可。
2. 复杂度分析：

• 时间复杂度：$O(n \log \max(nums))$。其中 $n$ 表示数组的长度。
• 空间复杂度：$O(1)$。

代码

class Solution {
public:
    int differenceOfSum(vector<int>& nums) {
        int sum1 = accumulate(nums.begin(), nums.end(), 0);
        int sum2 = 0;
        for (auto v : nums) {
            while (v != 0) {
                sum2 += (v % 10);
                v /= 10;
            }
        }
        return abs(sum1 - sum2);
    }
};

6292. 子矩阵元素加 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：

输入：n = 3, queries = [[1,1,2,2],[0,0,1,1]]
输出：[[1,1,0],[1,2,1],[0,1,1]]
解释：上图所展示的分别是：初始矩阵、执行完第一个操作后的矩阵、执行完第二个操作后的矩阵。
- 第一个操作：将左上角为 (1, 1) 且右下角为 (2, 2) 的子矩阵中的每个元素加 1 。 
- 第二个操作：将左上角为 (0, 0) 且右下角为 (1, 1) 的子矩阵中的每个元素加 1 。 

示例 2：

输入：n = 2, queries = [[0,0,1,1]]
输出：[[1,1],[1,1]]
解释：上图所展示的分别是：初始矩阵、执行完第一个操作后的矩阵。 
- 第一个操作：将矩阵中的每个元素加 1 。

提示：

• 1 <= n <= 500
• 1 <= queries.length <= 104
• 0 <= row1i <= row2i < n
• 0 <= col1i <= col2i < n

地址

https://leetcode.cn/contest/weekly-contest-328/problems/increment-submatrices-by-one/

题意

差分数组

思路

1. 题目初看起来比较复杂，实际我们可以计算每行的差分数组，即可计算出每个元素的数值。每个查询时，我们将 $[row1i,row2i]$ 中每一行的查分数组进行更新即可。或者直接使用二维差分数组，详细题解参考:题解
2. 复杂度分析：

• 时间复杂度：$O(nq)$，其中 $n$ 为给定的 $n$，$q$ 表示数组的长度。
• 空间复杂度：$O(n^2)$。

代码

• 一维差分

  class Solution { public: vector<vector<int>> rangeAddQueries(int n, vector<vector<int>>& queries) { int m = queries.size(); vector<vector<int>> cnt(n, vector<int>(n + 1)); for (int i = 0; i < m; i++) { int x1 = queries[i][0], y1 = queries[i][1]; int x2 = queries[i][2], y2 = queries[i][3]; for (int j = x1; j <= x2; j++) { cnt[j][y1]++; cnt[j][y2 + 1]--; } } vector<vector<int>> res(n, vector<int>(n)); for (int i = 0; i < n; i++) { int curr = 0; for (int j = 0; j < n; j++) { curr += cnt[i][j]; res[i][j] = curr; } } return res; } };

• 二维差分

  class Solution { public: vector<vector<int>> rangeAddQueries(int n, vector<vector<int>>& queries) { // 二维差分数组 vector<vector<int>> diff(n + 1, vector<int>(n + 1)); // +1 是为了避免特殊处理横纵坐标为 n 的点 for (vector<int>& q: queries) { int row1 = q[0]; int col1 = q[1]; int row2 = q[2] + 1; int col2 = q[3] + 1; diff[row1][col1]++; diff[row1][col2]--; diff[row2][col1]--; diff[row2][col2]++; } // 二维前缀和 vector<vector<int>> res(n, vector<int>(n)); // 第一个数 res[0][0] = diff[0][0]; // 第一行 for (int j = 1; j < n; ++j) { res[0][j] += res[0][j - 1] + diff[0][j]; } // 其余行 for (int i = 1; i < n; ++i) { res[i][0] = res[i - 1][0] + diff[i][0]; for (int j = 1; j < n; ++j) { res[i][j] = res[i - 1][j] + res[i][j - 1] - res[i - 1][j - 1] + diff[i][j]; } } return res; } };

6293. 统计好子数组的数目

给你一个整数数组 nums 和一个整数 k ，请你返回 nums 中 好 子数组的数目。

一个子数组 arr 如果有 至少k 对下标 (i, j) 满足 i < j 且 arr[i] == arr[j] ，那么称它是一个 好 子数组。

子数组 是原数组中一段连续 非空 的元素序列。

示例 1：

输入：nums = [1,1,1,1,1], k = 10
输出：1
解释：唯一的好子数组是这个数组本身。

示例 2：

输入：nums = [3,1,4,3,2,2,4], k = 2
输出：4
解释：总共有 4 个不同的好子数组：
- [3,1,4,3,2,2] 有 2 对。
- [3,1,4,3,2,2,4] 有 3 对。
- [1,4,3,2,2,4] 有 2 对。
- [4,3,2,2,4] 有 2 对。

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i], k <= 109

地址

https://leetcode.cn/contest/weekly-contest-328/problems/count-the-number-of-good-subarrays/

题意

滑动窗口

思路

1. 题目还算比较有意思的题目，我们用 $i$ 指向当前子数组的最右边的索引，我们只需要找到最左边的 $j$，此时满足子数组 $nums[j,\cdots,i]$ 为好子数组时，则此时以 $i$ 为结尾的好子数组的个数为 $j + 1$ 个，当前索引从 $0$ 开始。根据上面的思路，我们可以知道只需要快速的统计出 $[j,i]$ 知道的数对的数目即可，此时自然而然我们想到了利用哈希表即可。假设当前区间中元素 $nums[i]$ 个数位 $cnt[nums[i]]$, 此时加入 $nums[i]$ 后数对的个数增加 $cnt[nums[i]]$ 个，我们只需要连续计算即可。每次固定住右边的索引，移动左边的索引 $j$ 即可。
2. 复杂度分析

• 时间复杂度：时间复杂度为 $O(n)$，$n$ 表示字符的长度。
• 空间复杂度：时间复杂度为 $O(1)$。

代码

class Solution {
public:
    long long countGood(vector<int>& nums, int k) {
        unordered_map<int, int> cnt;
        long long res = 0, curr = 0;
        for (int i = 0, j = 0; i < nums.size(); i++) {
            curr += cnt[nums[i]];
            cnt[nums[i]]++;
            if (curr >= k) {
、                while (j <= i && curr - cnt[nums[j]] + 1 >= k) {
                    cnt[nums[j]]--;
                    curr -= cnt[nums[j]];
                    j++;
                }
                res += (j + 1);
            }
        }
        return res;
    }
};

6294. 最大价值和与最小价值和的差值

给你一个 n 个节点的无向无根图，节点编号为 0 到 n - 1 。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间有一条边。

每个节点都有一个价值。给你一个整数数组 price ，其中 price[i] 是第 i 个节点的价值。

一条路径的 价值和 是这条路径上所有节点的价值之和。

你可以选择树中任意一个节点作为根节点 root 。选择 root 为根的 开销 是以 root 为起点的所有路径中，价值和 最大的一条路径与最小的一条路径的差值。

请你返回所有节点作为根节点的选择中，最大 的 开销 为多少。

示例 1：

输入：n = 6, edges = [[0,1],[1,2],[1,3],[3,4],[3,5]], price = [9,8,7,6,10,5]
输出：24
解释：上图展示了以节点 2 为根的树。左图（红色的节点）是最大价值和路径，右图（蓝色的节点）是最小价值和路径。
- 第一条路径节点为 [2,1,3,4]：价值为 [7,8,6,10] ，价值和为 31 。
- 第二条路径节点为 [2] ，价值为 [7] 。
最大路径和与最小路径和的差值为 24 。24 是所有方案中的最大开销。

示例 2：

输入：n = 3, edges = [[0,1],[1,2]], price = [1,1,1]
输出：2
解释：上图展示了以节点 0 为根的树。左图（红色的节点）是最大价值和路径，右图（蓝色的节点）是最小价值和路径。
- 第一条路径包含节点 [0,1,2]：价值为 [1,1,1] ，价值和为 3 。
- 第二条路径节点为 [0] ，价值为 [1] 。
最大路径和与最小路径和的差值为 2 。2 是所有方案中的最大开销。

提示：

• 1 <= n <= 105
• edges.length == n - 1
• 0 <= ai, bi <= n - 1
• edges 表示一棵符合题面要求的树。
• price.length == n
• 1 <= price[i] <= 105

地址

https://leetcode.cn/contest/weekly-contest-328/problems/difference-between-maximum-and-minimum-price-sum/

题意

树上DP

思路

1. 题目说了一大堆，实际上题目并不复杂，重要的问题在于如何转化。题目要求找到最大价值和，价值和的定义为从根节点开始的最大的一条路径与最小的一条路径的差值。实际上我们仔细分析一下，有两点：

• 最大的路径一定为从根节点到某个叶子节点；
• 最小的路径一定为根节点本身；
  因此可以得到下面的结论:
• 最大的价值和的根节点一定为某个叶子节点；
• 最大的价值和即等于从叶子到某个非叶子节点的最大路径；

2. 根据以上分析以后题目就变得很简单了，我们只需要求出从叶子节点到非叶子节点的最大路径即可，此时我们可以利用树上 $dp$，每次返回以节点 $p$ 为根节点，求出 $p$ 到以 $p$ 为根节点的子树下面的叶子节点与非叶子节点的最大距离即可。我们很容易求出上述两个值，并求出 $p$ 的子树下叶子节点到非叶子节点的最大距离。
3. 复杂度分析：

• 时间复杂度：$O(V)$，其中 $V$ 表示节点的数目。我们只需要遍历一遍即可。
• 空间复杂度：$O(V + E)$。

代码

typedef pair<long long, long long> pll;

class Solution {
public:
    pll dfs(int root, long long &res, vector<bool> &visit, vector<vector<int>> &graph, vector<int>& price) {
        visit[root] = true;
        long long maxdist1 = price[root], maxdist2 = 0;
        for (auto next : graph[root]) {
            if (visit[next]) continue;
            auto [dist1, dist2] = dfs(next, res, visit, graph, price);
            res = max(res, max(maxdist1 + dist2, maxdist2 + dist1));
            maxdist1 = max(maxdist1, dist1 + price[root]);
            maxdist2 = max(maxdist2, dist2 + price[root]);
        }
        return {maxdist1, maxdist2};
    }
    
    long long maxOutput(int n, vector<vector<int>>& edges, vector<int>& price) {
        long long res = 0;
        vector<vector<int>> graph(n);
        for (auto v : edges) {
            graph[v[0]].emplace_back(v[1]);
            graph[v[1]].emplace_back(v[0]);
        }
        vector<bool> visit(n, false);
        dfs(0, res, visit, graph, price);
        return res;
    }
};

欢迎关注和打赏，感谢支持！

• 关注我的博客: http://whistle-wind.com/
• 关注我的知乎：https://www.zhihu.com/people/da-hua-niu
• 关注我的微信公众号: 公务程序猿