c2c网站价格,最新网页版传奇游戏排行榜,小程序商城源代码,交互做的不好的网站题目列表
2923. 找到冠军 I
2924. 找到冠军 II
2925. 在树上执行操作以后得到的最大分数
2926. 平衡子序列的最大和
一、找到冠军I 第一题模拟题#xff0c;简单来说是看每一行(列)是否全是1#xff0c;当然不包括自己比自己强的情况#xff0c;需要特判
代码如下 …题目列表
2923. 找到冠军 I
2924. 找到冠军 II
2925. 在树上执行操作以后得到的最大分数
2926. 平衡子序列的最大和
一、找到冠军I 第一题模拟题简单来说是看每一行(列)是否全是1当然不包括自己比自己强的情况需要特判
代码如下
class Solution {
public:int findChampion(vectorvectorint grid) {int ngrid.size();for(int i0;in;i){int j;for(j0;jn;j){if(i!jgrid[i][j]0){break;}}if(jn)return i;}return -1;}
};
二、找到冠军II 这题和上题相似但是所给的数据内容不同。只要看图中是否只有一个结点的入度为0就行
代码如下
class Solution {
public:int findChampion(int n, vectorvectorint edges) {vectorintdeg(n);for(autoe:edges){int ye[1];deg[y];}int ans-1;for(int i0;in;i){if(!deg[i]){if(ans!-1)return -1;ansi;}}return ans;}
};
三、在树上执行操作以后得到的最大分数 这题的题目意思是让这棵树的每条路径和都0同时让自己获得的分数最大
如果正着思考我们就要考虑选哪些点使得我们获得的分数最大同时保持树的健康这样思考无论是从上往下走还是从上往下走我们都要去考虑遍历到的结点的上下两边的情况比较麻烦
那么正难则反如果我们逆着思考即考虑选哪些结点留在树上那么我们就可以边遍历边找最小值然后用 总价值 减去 留在书上的最小值 得到答案
代码如下
class Solution {typedef long long LL;
public:long long maximumScoreAfterOperations(vectorvectorint edges, vectorint values) {int nvalues.size();vectorvectorintg(n);for(autoe:edges){int xe[0],ye[1];g[x].push_back(y);g[y].push_back(x);}//该dfs函数用来计算一棵树的每条路径上的最小值之和functionLL(int,int)dfs[](int x,int fa)-LL{LL res0;for(int y:g[x]){if(y!fa){resdfs(y,x);}}return res0?values[x]:min((LL)values[x],res);//如果res0说明是叶子节点直接返回结点值};LL saccumulate(values.begin(),values.end(),0LL);return s-dfs(0,-1);}
};
四、平衡子序列的最大和 正常来说求子序列的最大元素和用动态规划就行这题有点特殊需要优化时间复杂度我们先来看看正常的动规的写法
思路将题目给的不等式移项得到num[ i ] - i nums[ j ] - j这样我们就将两个相互影响的值变成了只和自己有关的nums[i]-i我们用数组b存放nums[i] - i
动规
dp数组含义dp[i]表示以i为结尾的最大元素和
递推公式dp[i]max(dp[j]0)nums[i] 条件 ji b[j]b[i]
初始化具体在代码答案为max(dp[i])
class Solution {
public:typedef long long LL;long long maxBalancedSubsequenceSum(vectorint nums) {int nnums.size();LL ansINT_MIN;vectorLLdp(nums.begin(),nums.end());for(int i0;in;i){for(int ji-1;j0;j--){if(nums[i]-inums[j]-j)dp[i]max(dp[j]nums[i],dp[i]);}ansmax(dp[i],ans);}return ans;}
};
上面代码的时间复杂度是O(n^2)数据范围太大过不了那么如何优化时间复杂度
上面代码最浪费时间的是 dp[i]max(dp[j])nums[i] 这行代码即查找最大值速度慢了那么我们怎么才能提高查找的速度这里就要引入一个数据结构---树状数组它其实和线段树相似是线段树的子集。
如果没听过的可以去了解一下这里不具体讲它的原理
(这里推荐一个视频讲得很简洁明了五分钟丝滑动画讲解 | 树状数组_哔哩哔哩_bilibili )
树状数组适合维护前缀和/前缀最大值单点更新这类题目更新和查询的时间复杂度均为O(logn)
而求 max(dp[j]) 不就是维护前缀最大值吗每当计算出一个dp[i]就去更新树状数组简直完美
现在还有一点需要注意我们怎么样去将b[i]和树状数组的下标映射起来这里又有一个知识点离散化【复制排序去重】具体看代码这个就是几行代码的事很简单的
(这里有人可能会对将b[i]和树状数组的下标映射这点感到疑惑因为我们上面分析的是对dp数组的前缀最大值进行维护才对解释一下我们的递推公式有两个条件ji b[j]b[i]我们是从左往右遍历的所以更新到树状数组中的值全部满足ji的情况即我们只要考虑b[j]b[i]这个条件就行那么我们对b数组排序之后映射到树状数组的下标后自然就满足这个条件了我们只要在比b[i]小的b[j]元素对应的dp[i]中求最大值就行即求前缀最大值)
代码如下
typedef long long LL;
class BIT{ vectorLLbit;
public:BIT(int n):bit(n,LLONG_MIN){}void updata(int i,LL data){while(ibit.size()){bit[i]max(bit[i],data);i(i-i);}}LL pre_max(int i){LL resLLONG_MIN;while(i0){resmax(res,bit[i]);i(i-1);}return res;}
};
class Solution {
public:long long maxBalancedSubsequenceSum(vectorint nums) {int nnums.size();vectorintb(n);//离散化//1.复制for(int i0;in;i)b[i]nums[i]-i;//2.排序sort(b.begin(),b.end());//3.去重b.erase(unique(b.begin(),b.end()),b.end());LL ansLLONG_MIN;BIT tree(n1);for(int i0;in;i){int jlower_bound(b.begin(),b.end(),nums[i]-i)-b.begin()1;//计算下标LL datamax(0LL,tree.pre_max(j))nums[i];tree.updata(j,data);ansmax(ans,data);}return ans;}
};
