6291. Difference Between Element Sum and Digit Sum of an Array
给你一个正整数数组 nums 。
- 元素和 是 nums 中的所有元素相加求和。
- 数字和 是 nums 中每一个元素的每一数位（重复数位需多次求和）相加求和。
返回 元素和 与 数字和 的绝对差。
注意：两个整数 x 和 y 的绝对差定义为 |x - y| 。
测试样例
输入：nums = [1,15,6,3]
输出：9
解释：
nums 的元素和是 1 + 15 + 6 + 3 = 25 。
nums 的数字和是 1 + 1 + 5 + 6 + 3 = 16 。
元素和与数字和的绝对差是 |25 - 16| = 9 。
解答：本地按照题意，计算元素和数位，取绝对差即可。详细看代码
class Solution {
public int differenceOfSum(int[] nums) {
int sum = 0, digitSum = 0;
for (int i : nums) {
sum += i;
digitSum += digit(i);
}
return Math.abs(sum - digitSum);
}
private int digit(int n) {
int res = 0;
while (n > 0) {
res += (n % 10);
n /= 10;
}
return res;
}
}6292. Increment Submatrices by One
给你一个正整数 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 。
测试样例：
输入：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 。
解答: 这道题目乍一看，真的感觉很难。一开始以为会用到二维的线段树。但是题目给了一系列很重要的提示：
- 1 <= n <= 500
- 1 <= queries.length <= 10^4
这个范围，用二阶矩阵，记录每行的修改位置，最后计算前缀和即可
class Solution {
public int[][] rangeAddQueries(int n, int[][] queries) {
int[][] res = new int[n][n];
int[][] mem = new int[n + 1][n + 1];
for (int[] q : queries) {
for (int i = q[0]; i <= q[2]; ++i) {
mem[i][q[1]] += 1;
mem[i][q[3] + 1] -= 1;
}
}
for (int i = 0; i < n; ++i) {
int sum = 0;
for (int j = 0; j < n; ++j) {
sum += mem[i][j];
res[i][j] = sum;
}
}
return res;
}
}6293. Count the Number of Good Subarrays
给你一个整数数组 nums 和一个整数 k ，请你返回 nums 中 好 子数组的数目。
一个子数组 arr 如果有 至少 k 对下标 (i, j) 满足 i < j 且 arr[i] == arr[j] ，那么称它是一个 好 子数组。
子数组 是原数组中一段连续非空的元素序列。
测试样例
输入：nums = [1,1,1,1,1], k = 10
输出：1
解释：
唯一的好子数组是这个数组本身。
解答：这道题目说到子数组（连续非空元素序列），加上数字越多则满足要求的(i,j)对必然是单调上升的。所以我们可以尝试使用双指针来寻找，以某个断点开始，满足要求的最短长度。
每次更新的时候，利用HashMap记录一个数字的出现次数。则每增加一个相同的数字，就是增加之前出现的数量。减去一个数字，也是类似的逻辑。具体可以看代码。
PS：这题还需要注意，返回是long，不要使用int导致答案出错。
class Solution {
public long countGood(int[] nums, int k) {
HashMap<Integer, Integer> map = new HashMap<>();
int left = 0, right = 0;
long count = 0, res = 0;
while (left < nums.length) {
while (count < k && right < nums.length) {
int o = map.getOrDefault(nums[right], 0);
count += o;
map.put(nums[right], o + 1);
++right;
}
if (count >= k) {
res += (nums.length - right + 1);
} else {
break;
}
int tmp = map.get(nums[left]) - 1;
count -= tmp;
map.put(nums[left], tmp);
++left;
}
return res;
}
}6294. Difference Between Maximum and Minimum Price Sum
给你一个 n 个节点的无向无根图，节点编号为 0 到 n - 1 。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间有一条边。
每个节点都有一个价值。给你一个整数数组 price ，其中 price[i] 是第 i 个节点的价值。
一条路径的 价值和 是这条路径上所有节点的价值之和。
你可以选择树中任意一个节点作为根节点 root 。选择 root 为根的 开销 是以 root 为起点的所有路径中，价值和 最大的一条路径与最小的一条路径的差值。
请你返回所有节点作为根节点的选择中，最大 的 开销 为多少。
测试样例：
输入：n = 6, edges = [[0,1],[1,2],[1,3],[3,4],[3,5]], price = [9,8,7,6,10,5]
输出：24
解释：
- 第一条路径节点为 [2,1,3,4]：价值为 [7,8,6,10] ，价值和为 31 。
- 第二条路径节点为 [2] ，价值为 [7] 。
最大路径和与最小路径和的差值为 24 。24 是所有方案中的最大开销。
解答：这道题目其实难度不大。如果你做过834. Sum of Distances in Tree。此题的逻辑也是类似的。需要使用到树形的动态规划。
我们假设0是根。以0为开头进行遍历，利用第一个函数buildTopTwoExceptParent，我们可以得到每个节点除开父节点所能得到的最大路径和。
但是题目要求所有节点作为根节点的选择。那么逻辑也很简单，在第二次利用findBest遍历的时候，我们将父节点的最大，路径传给子节点。然后子节点根据自己的动态规划矩阵和父节点的情况计算自己的作为根节点的最大值即可。
PS：这题还需要注意，返回是long，不要使用int导致答案出错。
class Solution {
public long maxOutput(int n, int[][] edges, int[] price) {
List<Integer>[] graph = new List[n];
for (int i = 0; i < n; ++i) {
graph[i] = new ArrayList<>();
}
for (int[] e : edges) {
graph[e[0]].add(e[1]);
graph[e[1]].add(e[0]);
}
long[][][] mem = new long[n][2][];
buildTopTwoExceptParent(0, -1, graph, price, mem);
long[] res = {0};
findBest(0, -1, 0, graph, price, mem, res);
return res[0];
}
private long buildTopTwoExceptParent(int cur, int pre, List<Integer>[] graph, int[] prices, long[][][] mem) {
long res = 0;
for (int i : graph[cur]) {
if (i != pre) {
long tmp = buildTopTwoExceptParent(i, cur, graph, prices, mem);
if (mem[cur][0] == null || mem[cur][0][0] < tmp) {
mem[cur][1] = mem[cur][0];
mem[cur][0] = new long[]{tmp, i};
res = tmp;
} else if (mem[cur][1] == null || mem[cur][1][0] < tmp) {
mem[cur][1] = new long[]{tmp, i};
}
}
}
return res + prices[cur];
}
private void findBest(int cur, int pre, long preSum, List<Integer>[] graph, int[] prices, long[][][] mem, long[] res) {
long best = preSum;
if (mem[cur][0] != null) {
best = Math.max(best, mem[cur][0][0]);
}
res[0] = Math.max(res[0], best);
for (int i : graph[cur]) {
if (i != pre) {
if (i != mem[cur][0][1]) {
findBest(i, cur, best + prices[cur], graph, prices, mem, res);
} else {
long tmp = preSum;
if (mem[cur][1] != null) {
tmp = Math.max(tmp, mem[cur][1][0]);
}
findBest(i, cur, tmp + prices[cur], graph, prices, mem, res);
}
}
}
}
}这周的题目，需要绕点弯。但是题目难度总体不大。