全球网站流量排名100,上海技术公司做网站,网站备案必须做,网站快照前显示中文怎么做的题目列表
2873. 有序三元组中的最大值 I
2874. 有序三元组中的最大值 II
2875. 无限数组的最短子数组
2876. 有向图访问计数 一、有序三元组中的最大值I 看一眼该题的数据范围#xff0c;直接三层for循环暴力枚举#xff0c;时间复杂度O(n^3)#xff0c;代码如下
class…题目列表
2873. 有序三元组中的最大值 I
2874. 有序三元组中的最大值 II
2875. 无限数组的最短子数组
2876. 有向图访问计数 一、有序三元组中的最大值I 看一眼该题的数据范围直接三层for循环暴力枚举时间复杂度O(n^3)代码如下
class Solution {
public:long long maximumTripletValue(vectorint nums) {long long ans0;for(int i0;inums.size();i){for(int ji1;jnums.size();j){for(int kj1;knums.size();k){ansmax(ans,1LL*(nums[i]-nums[j])*nums[k]);}}}return ans;}
};
二、有序三元组的最大值II
题目同上一题只有数据范围不同 同一个题数据范围变大之后再用暴力就会超时我们要想想怎么优化时间复杂度
这里有三种思路
1.我们枚举i看jk怎么选
2.我们枚举j看ik怎么选
3.我们枚举k看ij怎么选
假设我们选择方案一枚举i(即先确定一个nums[ i ])那么nums[ j ]和nums[ k ]要如何选才能让三元组的值最大显然nums[ j ]要选最小的nums[ k ]选最大的这样三元组值最大但是还有一个条件jk这就很难办了 因为我们不能确定要选择的最小值和最大值的位置关系所以方案一不选
假设我们选择方案二枚举j(即先确定一个nums[ j ])那么nums[ i ]和nums[ k ]要如何选才能让三元组的值最大显然nums[ i ]选最大的nums[ k ]也选最大的这样三元组值最大并且ijk即我们选取的nums[ i ]和nums[ k ]是互不影响的我们只要预处理出前i个元素的最大值和后i个元素的最大值就能在O(n)的时间复杂度内找到答案代码如下
class Solution {
public:long long maximumTripletValue(vectorint nums) {int nnums.size();long long ans0;vectorintpre(n1),suf(n);pre[0]0;for(int i0;in;i)pre[i1]max(pre[i],nums[i]);for(int in-1;i1;i--)suf[i-1]max(suf[i],nums[i]);for(int j0;jn;j)ansmax(ans,1LL*(pre[j]-nums[j])*suf[j]);return ans;}
};//当然这里的前缀最大值数组还可以优化掉
class Solution {
public:long long maximumTripletValue(vectorint nums) {int nnums.size();long long ans0;vectorintsuf(n);for(int in-1;i1;i--)suf[i-1]max(suf[i],nums[i]);for(int j1,prenums[0];jn;j){ansmax(ans,1LL*(pre-nums[j])*suf[j]);premax(pre,nums[j]);}return ans;}
};
假设我们选择方案三枚举k(即先确定一个nums[ k ])那么nums[ i ]和nums[ j ]要如何选才能让三元组的值最大即nums[ i ] - nums[ j ]要最大那么这不就是在遍历的过程中维护一个前缀最大值和一个最大高度差吗(估计有人不太能理解我画个折线图大家应该能好懂一些思路和121. 买卖股票的最佳时机很相似 代码如下
class Solution {
public:long long maximumTripletValue(vectorint nums) {int nnums.size();long long ans0;for(int k0,pre0,diff0;kn;k){ansmax(ans,1LL*diff*nums[k]);diffmax(diff,pre-nums[k]);premax(pre,nums[k]);}return ans;}
};
(大家可以试着将第二题的代码放到第一题去跑一跑对比一下两者的时间感受一下算法的魅力)
三、无限数组的最短子数组 看到找最短的子数组的和等于target第一个想到的就是滑动窗口当然这题和正常的滑窗有点不同它给的数组是个可以循环的无限长数组。
我们要弄明白两个问题
1.我们需要一直遍历到无限远吗不需要我们的left端点只要在2倍的该数组里面遍历就行因为一旦超过这个范围后面的就又会开始循环之前遍历的结果没有任何意义。
2.如果targetsum(nums) 我们的子数组还需要从0开始增加长度吗不用因为不论怎么枚举子数组的长度都会有length(nums)*(target/sum(nums))的基础长度我们只要关心target%sum(nums)这部分的最小子数组的长度就可以了这样我们就将子数组差分成了两个部分一个是以整个数组为单位的一个是单独考虑的。
当然肯定有人会怀疑我们这种想法是不是太想当然了万一这两部分不能形成一个子数组怎么办好这里我们就构造一个这样的子数组我们假定找到了单独考虑的那部分子数组然后我们继续向后延伸由于数组是循环的所以我们总能找到和原数组长度一样的值相等的区间如此循环就能构造出我们想要的最短子数组即上面的想法正确
代码如下
class Solution {
public:typedef long long LL;int minSizeSubarray(vectorint nums, int target) {LL sumaccumulate(nums.begin(),nums.end(),0LL);int nnums.size();int s0,ansINT_MAX;for(int left0,right0;right2*n;right){snums[right%n];while(s(target%sum)){s-nums[left%n];left;}if(s(target%sum)) ansmin(ans,right-left1);}if(ansINT_MAX)return -1;return anstarget/sum*n;}
};
四、有向图访问计数 这是一个求每个结点向下能访问多少个不同结点的问题我们需要用拓扑排序将每个环从图中拆下来单独考虑得到换上每个结点的访问个数然后利用返图计算不在环上的点的访问个数
代码如下
class Solution {
public:vectorint countVisitedNodes(vectorint edges) {int nedges.size();vectorvectorintg(n);//反图vectorintdeg(n);//入度for(int i0;in;i){g[edges[i]].push_back(i);deg[edges[i]];}//拓扑排序queueintq;//存放入读为0的点for(int i0;in;i){if(deg[i]0)q.push(i);}//将不在环上的结点从图中去掉指的是将结点的入度设置为0while(!q.empty()){int xq.front();q.pop();if(--deg[edges[x]]0)q.push(edges[x]);}vectorintans(n);//计算不在环上的点functionvoid(int,int)dfs[](int x,int depth){ans[x]depth;for(int y:g[x]){if(deg[y]0){//环上的点入度为-1这里只遍历不在环上的点dfs(y,depth1);}}};for(int i0;in;i){if(deg[i]0) continue;//先计算环上的点的个数vectorintnode;for(int xi;;xedges[x]){node.push_back(x);deg[x]-1;//被计算过的环上的点的入度设为-1if(edges[x]i)break;}for(int x:node){dfs(x,node.size());}}return ans;}
};
