周赛328总结
第三题思路正确，但是但是卡在了返回结果用了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 ( n l o g U ) O(nlogU)O (n l o gU ),U = m a x ( n u m s ) U=max(nums)U =ma x (n u m s )
- 空间复杂度：O ( 1 ) O(1)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</code"> 和 <code>col1i <= y <="col2i</code"> 的 <code>mat[x][y]</code> 加 <code>1</code> 。<!--=--></code><!--=-->
返回执行完所有操作后得到的矩阵 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 ) O(n^2*q)O (n 2 ∗q )，q q q为q u e r i e s queries q u er i es的长度
- 空间复杂度：O ( 1 ) O(1)O (1 )
二维差分
前置知识：二维差分数组与二维前缀和数组
- 思路：使用二维差分数组记录每个区域的变化量，然后通过二维前缀和数组求得每个位置的值
- 实现
- 二维差分数组
div中的每一个格子记录的是「以当前位置为区域的 左上角（区域右下角恒定为原数组的右下角）的值的 变化量」【应该不固定 可以倒转】 - 二维差分数组的二维前缀和数组
sum，即差分数组 以当前位置为右下角，原数组的左上角为左上角的区域和 - 因此，如果要求 ( x 1 , y 1 ) (x1, y1)(x 1 ,y 1 ) 作为左上角，( x 2 , y 2 ) (x2, y2)(x 2 ,y 2 ) 作为右下角的区域值增加x x x的时候，可以利用二维差分数组快速求解，此时相当于二维差分矩阵上对( x 1 , y 1 ) (x1,y1)(x 1 ,y 1 )增加x x x，对( x 2 + 1 , y 1 ) (x2+1,y1)(x 2 +1 ,y 1 )和( x 1 , y 2 + 1 ) (x1,y2+1)(x 1 ,y 2 +1 )减小x x x，再对重复区域( x 2 + 1 , y 2 + 1 ) (x2+1,y2+1)(x 2 +1 ,y 2 +1 )增加x x x
- 要求得二维数组每个位置( x 1 , y 1 ) (x1,y1)(x 1 ,y 1 )的变化量，即求二维差分数组的二维前缀和数组
sum，即差分数组 以当前位置为右下角，原数组的左上角为左上角的区域和
s u m [ i , j ] = s u m [ i − 1 ] [ j ] + s u m [ i ] [ j − 1 ] − s u m [ i − 1 ] [ j − 1 ] + d e v [ i ] [ j ] sum[i,j] = sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+dev[i][j]s u m [i ,j ]=s u m [i −1 ][j ]+s u m [i ][j −1 ]−s u m [i −1 ][j −1 ]+d e v [i ][j ]- 初始时div数组需要扩展边界，转化为
sum时需要处理0
- 初始时div数组需要扩展边界，转化为
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 ) O(n^2+q)O (n 2 +q )，q q q为q u e r i e s queries q u er i es的长度
- 空间复杂度：O ( 1 ) O(1)O (1 )
+ div数组边界可以+2，方便处理0 d i v [ 1 : n ] [ 1 : n ] div[1:n][1:n]d i v [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 ] [0,l][0 ,l ]，对结果的贡献为l + 1 l+1 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);
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(n)O (n )
- 空间复杂度：O ( 1 ) O(1)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);
}
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)O (n )
- 空间复杂度：O ( n ) O(n)O (n )
Original: https://blog.csdn.net/Tikitian/article/details/128738191
Author: TIkitianya
Title: 周赛328总结
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/812039/
转载文章受原作者版权保护。转载请注明原作者出处！