第三题思路正确，但是但是卡在了返回结果用了int变量…很是无语
二维前缀和二维差分get
数组元素和与数字和的绝对差【LC2535】
给你一个正整数数组 nums 。
- 元素和 是 nums 中的所有元素相加求和。
- 数字和 是 nums 中每一个元素的每一数位（重复数位需多次求和）相加求和。
返回 元素和 与 数字和 的绝对差。
**注意：**两个整数 x 和 y 的绝对差定义为 |x - y| 。
- 思路：遍历数组中的元素，使用一个变量记录元素和减去数位和的差值
- 实现
class Solution { public int differenceOfSum(int[] nums) { int res = 0; for (int num : nums){ res += num; int x = num; while (x > 0){ res -= x % 10; x /= 10; } } return res; } }
。复杂度
- 时间复杂度：O(nlogU),U =max(nums)
- 空间复杂度：O(1)
子矩阵元素加 1【LC2536】
给你一个正整数 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 。
暴力
java过了…
class Solution { public int[][] rangeAddQueries(int n, int[][] queries) { int[][] mat = new int[n][n]; for (int[] query : queries){ int row1 = query[0], col1 = query[1], row2 = query[2], col2 = query[3]; for (int i = row1; i <= row2; i++){ for (int j = col1; j <= col2; j++){ mat[i][j]++; } } } return mat; } }
- 复杂度
。时间复杂度：O ( n 2 ∗ q ) ，q为queries的长度
。空间复杂度：O(1)
二维差分
前置知识：二维差分数组与二维前缀和数组
- 思路：使用二维差分数组记录每个区域的变化量，然后通过二维前缀和数组求得每个位置的值
- 实现
。二维差分数组div中的每一个格子记录的是「以当前位置为区域的左上角（区域右下角恒定为原数组的右下角）的值的变化量」【应该不固定 可以倒转】
。二维差分数组的二维前缀和数组sum，即差分数组以当前位置为右下角，原数组的左上角为左上角的区域和
。因此，如果要求 (x1,y1) 作为左上角，(x2,y2) 作为右下角的区域值增加x的时候，可以利用二维差分数组快速求解，此时相当于二维差分矩阵上对(x1,y1)增加x ，对(x2+1,y1)和(x1,y2+1)减小x，再对重复区域(x2+1,y2+1)增加x
。要求得二维数组每个位置(x1,y1)的变化量，即求二维差分数组的二维前缀和数组sum，即差分数组以当前位置为右下角，原数组的左上角为左上角的区域和
sum[i,j]=sum[i−1][j]+sum[i][j−1]−sum[i−1][j−1]+dev[i][j]
- 初始时div数组需要扩展边界，转化为sum时需要处理0
class Solution { public int[][] rangeAddQueries(int n, int[][] queries) { int[][] div = new int[n + 1][n + 1]; for (int[] q : queries){ div[q[0]][q[1]]++; div[q[0]][q[3] + 1]--; div[q[2] + 1][q[1]]--; div[q[2] + 1][q[3] + 1]++; } int[][] sum = new int[n][n]; for (int i = 0; i < n; i++){ for (int j = 0; j < n; j++){ sum[i][j] = div[i][j]; if (i != 0) sum[i][j] += sum[i - 1][j]; if (j != 0) sum[i][j] += sum[i][j - 1]; if (i != 0 && j != 0) sum[i][j] -= sum[i - 1][j - 1]; } } return sum; } }
- 复杂度
- 时间复杂度：O ( n 2 + q )，q 为queries的长度
- 空间复杂度：O(1)
- div数组边界可以+2，方便处理0
div[1:n][1:n]计算为二维前缀和数组，在赋值给结果集
class Solution { public int[][] rangeAddQueries(int n, int[][] queries) { int[][] div = new int[n + 2][n + 2]; for (int[] q : queries){ div[q[0] + 1][q[1] + 1]++; div[q[0] + 1][q[3] + 2]--; div[q[2] + 2][q[1] + 1]--; div[q[2] + 2][q[3] + 2]++; } int[][] sum = new int[n][n]; for (int i = 1; i <= n; i++){ for (int j = 1; j <= n; j++){ sum[i - 1][j - 1] = (div[i][j] += div[i - 1][j] + div[i][j - 1] - div[i - 1][j - 1]); } } return sum; } }
- 拓展：子矩阵元素变化量不定
统计好子数组的数目【LC2537】
给你一个整数数组 nums 和一个整数 k ，请你返回 nums 中 好 子数组的数目。
一个子数组 arr 如果有 至少 k 对下标 (i, j) 满足 i < j 且 arr[i] == arr[j] ，那么称它是一个 好 子数组。
子数组 是原数组中一段连续 非空 的元素序列。
- 思路：使用哈希表valToCount记录每个数字出现的次数，然后枚举子数组右端点r，那么新增的对数为valToCount.get(nums[r])，然后当总对数大于等于k时，将左端点l移动到最远的位置，那么当右端点为r时，合法的左端点为[0,l]，对结果的贡献为l+1。
- 实现
class Solution { public long countGood(int[] nums, int k) { int n = nums.length; int pair = 0; long res = 0; Map<Integer,Integer> intToCount = new HashMap<>(); int l = 0; for (int r = 0; r < n; r++){ pair += intToCount.getOrDefault(nums[r], 0); intToCount.put(nums[r], intToCount.getOrDefault(nums[r], 0) + 1); // 如果子数组对数大于k，那么右移左边界至最大可以去到的值 while(pair - intToCount.get(nums[l]) + 1 >= k && l < n){ intToCount.put(nums[l], intToCount.get(nums[l]) - 1); pair -= intToCount.get(nums[l]); l++; } if (pair >= k){ res += l + 1; } } return res; } }
。复杂度
- 时间复杂度：O ( n )
- 空间复杂度：O ( 1 )
最大价值和与最小价值和的差值【LC2538】
给你一个 n 个节点的无向无根图，节点编号为 0 到 n - 1 。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间有一条边。
每个节点都有一个价值。给你一个整数数组 price ，其中 price[i] 是第 i 个节点的价值。
一条路径的 价值和 是这条路径上所有节点的价值之和。
你可以选择树中任意一个节点作为根节点 root 。选择 root 为根的 开销 是以 root 为起点的所有路径中，价值和 最大的一条路径与最小的一条路径的差值。
请你返回所有节点作为根节点的选择中，最大 的 开销 为多少。
树形dp
- 思路：
。由于价值都是正数，因此价值和最小的一条路径一定只有一个点。那么，「价值和最大的一条路径与最小的一条路径的差值」等价于「去掉路径的一个端点」，因此问题可以转化为问题转换成去掉一个叶子后的最大路径和（这里的叶子严格来说是度为 1 的点，因为根的度数也可能是 1）。
使用树形dp找到去掉一个叶子后的最大路径和：在树上做DFS，递归到最底层的叶子节点，再一层层返回当前带叶子的路径和」和「当前不带叶子的路径和」更新至根结点，对于根节点而言，答案的可能性有两种：
- 前面最大带叶子的路径和 + 当前不带叶子的路径和；
- 前面最大不带叶子的路径和 + 当前带叶子的路径和；
然后更新「最大带叶子的路径和」和「最大不带叶子的路径和」以及结果。
- 实现
。使用邻接表存储二叉树
。然后使用树形dp将结果一层一层返回至根节点，由于每个节点只遍历一次，因此不需要写成记忆化搜索的形式，当遇到更大的值时，更新结果
class Solution { private List<Integer>[] g; private int[] price; private long ans; public long maxOutput(int n, int[][] edges, int[] price) { this.price = price; g = new ArrayList[n]; Arrays.setAll(g, e -> new ArrayList<>()); for (var e : edges) { int x = e[0], y = e[1]; g[x].add(y); g[y].add(x); // 建树 } dfs(0, -1); return ans; } // 返回带叶子的最大路径和，不带叶子的最大路径和 private long[] dfs(int x, int fa) { long p = price[x], maxS1 = p, maxS2 = 0; for (var y : g[x]) if (y != fa) { var res = dfs(y, x); long s1 = res[0], s2 = res[1]; // 前面最大带叶子的路径和 + 当前不带叶子的路径和 // 前面最大不带叶子的路径和 + 当前带叶子的路径和 ans = Math.max(ans, Math.max(maxS1 + s2, maxS2 + s1)); maxS1 = Math.max(maxS1, s1 + p); maxS2 = Math.max(maxS2, s2 + p); // 这里加上 p 是因为 x 必然不是叶子 } return new long[]{maxS1, maxS2}; } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/difference-between-maximum-and-minimum-price-sum/solutions/2062782/by-endlesscheng-5l70/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
。复杂度
- 时间复杂度：O ( n )
- 空间复杂度：O ( n )
