关注、星标下方公众号，和你一起成长

作者 | 梁唐

(相关资料图)

出品 | 公众号：Coder梁（ID：Coder_LT）

大家好，我是梁唐。

今天是周一，我们照惯例来看看昨天的LeetCode周赛。

这次是LeetCode周赛第328场，这一次同样是官方的福利场。所有通过一题的同学都可以获得官方的学习专属福利。

这场的赛题难度不低，尤其对于初学者而言，可能从第二题开始就会开始很棘手。不少同学也在评论区里吐槽了难度，但不考虑比赛，仅考虑对算法能力的锻炼程度来看的话，那还是很值得一做的。

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

给你一个正整数数组 nums。

返回 元素和与 数字和的绝对差。

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

题解

签到题，这里我懒得将数字按位拆分了。直接使用Python将数字转化成字符串，再对字符串进行求和。

classSolution:defdifferenceOfSum(self,nums:List[int])->int:s1=sum(nums)s2=0forninnums:st=str(n)forsinst:s2+=ord(s)-ord("0")returnabs(s1-s2)

子矩阵元素加 1

给你一个正整数 n，表示最初有一个 n x n、下标从 0开始的整数矩阵 mat，矩阵中填满了 0 。

另给你一个二维整数数组 query。针对每个查询 query[i] = [row1i, col1i, row2i, col2i]，请你执行下述操作：

返回执行完所有操作后得到的矩阵 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覆盖了两次，所以要再加回来。

直接写二维差分可能会比较棘手，可以先从一维开始理解会容易一些。

classSolution{public:vector>rangeAddQueries(intn,vector>&queries){vector>diff(n+2,vector(n+2,0));for(auto&q:queries){intr1=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>ret(n,vector(n,0));for(inti=0;i

统计好子数组的数目

给你一个整数数组 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。

剩下的问题是如何判断子数组是否是好的，其实非常简单。当区间内增加一个新的元素时，它只能和区间内同样的元素配对。区间内有几个值相同的元素，就能增加几个配对。所以我们只需要维护一下区间内各个元素的数量即可。

classSolution{public:longlongcountGood(vector&nums,intk){longlongret=0;intl=0;intn=nums.size();mapmp;longlongtmp=0;for(intr=0;r=k){tmp-=mp[nums[l]]-1;mp[nums[l++]]--;}if(tmp>=k)ret+=l+1;}returnret;}};

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

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

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

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

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

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

题解

由每个节点的值都为正数，很容易发现所谓最大路径减去最小路径，即为最大路径减去较小的一个端点。

剩下的问题就是怎么求这个最大的路径，因为树中的节点数是1e5，显然我们不能枚举每一个节点作为根节点。针对这个问题，如果大家对于树结构比较熟悉的话，其实可以发现不论当前的根节点是谁，答案的可能性都只有两种。

假设当前根节点是r，分别是：

classSolution{public:longlongmaxOutput(intn,vector>&edges,vector&price){vectorgraph[n+2];//建图for(auto&vt:edges){intu=vt[0],v=vt[1];graph[u].push_back(v);graph[v].push_back(u);}longlongret=0;function(int,int)>dfs=[&](intu,intf){//fst为子树中包含u的最大路径，sed为不包含叶子的最大路径longlongfst=price[u],sed=0;for(autov:graph[u]){if(v==f)continue;autocur=dfs(v,u);longlongfs=cur.first,se=cur.second;//se+fst为子树v中不包含叶子的最大路径+其他子树包含叶子的值//fs+sed为子树v包含叶子+其他子树不包含叶子ret=max({ret,se+fst,fs+sed});//子树v包含叶子连上节点ufst=max(fst,fs+price[u]);//子树v不包含叶子连上节点used=max(sed,se+price[u]);}returnmake_pair(fst,sed);};dfs(0,-1);returnret;}};