申请一个域名后怎么做网站,evernote wordpress,手机版网站打开速度慢,一流校建设网站题目列表
2864. 最大二进制奇数
2865. 美丽塔 I
2866. 美丽塔 II
2867. 统计树中的合法路径数目
一、最大二进制奇数 这题只要你对二进制有了解(学编程的不会不了解二进制吧)#xff0c;应该问题不大#xff0c;这题要求最大奇数#xff0c;1.奇数#xff1a;只要保证…题目列表
2864. 最大二进制奇数
2865. 美丽塔 I
2866. 美丽塔 II
2867. 统计树中的合法路径数目
一、最大二进制奇数 这题只要你对二进制有了解(学编程的不会不了解二进制吧)应该问题不大这题要求最大奇数1.奇数只要保证二进制的最低位上是1就行这里为不了解二进制的同学解释一下二进制从低位到高位的权重分别是2^02^12^2...即除了最低位其他位都是偶数所以最低位必须是1
2.最大贪心我们将除了最低位的1之外的所有1都往高位放得到的数肯定是最大的
代码如下
class Solution {
public:string maximumOddBinaryNumber(string s) {int cnt1count(s.begin(),s.end(),1);return string(cnt1-1,1)string(s.size()-cnt1,0)1;}
};
二、美丽塔I 这题的数据范围比较小可以直接暴力将每一个元素都当成山顶算一遍最大高度然后比较得到最大高度代码如下
class Solution {
public:long long maximumSumOfHeights(vectorint maxHeights) {long long ans0;int nmaxHeights.size();for(int i0;in;i){long long resmaxHeights[i];for(int ji-1,MinmaxHeights[i];j0;j--){Minmin(Min,maxHeights[j]);resMin;}for(int ji1,MinmaxHeights[i];jn;j){Minmin(Min,maxHeights[j]);resMin;}ansmax(ans,res);}return ans;}
};
三、美丽塔II
这题的题目和上一题一样只是加大了数据范围即不能用暴力枚举的方法解题那么我们怎么优化算法呢关键在于发现上面一题的算法中有什么是被重复计算的我们只要减少这些无用的运算就能实现算法的时间复杂度优化。
为了方便叙述我将山顶前面的部分称为上坡山顶后面的部分称为下坡很显然上面算法在每次计算上坡/下坡时总是不断的遍历之前就已经遍历过的元素那么我们如何根据已经遍历过的元素来求出当前的上坡/下坡的高度呢而且上坡和下坡的计算是分开的互不影响的只要我们提前处理出各种上坡和下坡的高度我们就能在O(n)的时间里得到最大高度。
如何利用之前遍历的元素信息得到当前的上坡/下坡的高度以计算上坡为例解析如下 代码如下
class Solution {
public:long long maximumSumOfHeights(vectorint maxHeights) {long long ans0;int nmaxHeights.size();vectorlong longpre(n),suf(n);//分别代表以i为山顶的上坡和下坡stackintst;//里面存放下标方便计算出栈个数和索引高度st.push(-1);//这里是为了方便计算简化逻辑for(int i0;in;i){while(st.size()1maxHeights[i]maxHeights[st.top()])st.pop();int idxst.top();pre[i](idx0?0:pre[idx])1LL*(i-st.top())*maxHeights[i];st.push(i);}ststackint();//让栈为空st.push(n);//这里是为了方便计算简化逻辑for(int in-1;i0;i--){while(st.size()1maxHeights[i]maxHeights[st.top()])st.pop();int idxst.top();suf[i](idxn?0:suf[idx])1LL*(st.top()-i)*maxHeights[i];st.push(i);}for(int i0;in;i){ansmax(ans,pre[i]suf[i]-maxHeights[i]);}return ans;}
};
这里说明一下算法的时间复杂度为O(n)有人或许看到求pre/suf中有两层循环就认为时间复杂度为O(n^2)但其实不是我们来看一下while循环里面的出栈语句执行了多少次因为我们入栈的元素是n个所以出栈的元素也只能是n个所以这条语句只能执行n次所以时间复杂度为O(n)
四、统计树种的合法路径数量 这题求路径个数首先读懂题意要求路径上包含一个质数那么我们是从质数出发好还是从非质数出发好呢我们只要稍稍想一下就会发现从质数出发好因为这样我们只要找到下一个质数就停止而从非质数出发我们就需要连续找到两个质数很显然从非质数出发要处理的情况更多所以我们从质数出发找路径当然注意这题的路径至少需要两个结点(看示例一)
那么我们从质数出发怎么算呢(判断质数就不讲了不会的可以去看Leetcode-352周赛的第二题) 其他的路径求解方法同上代码如下
//埃氏筛
const int MX1e5;
vectorboolis_prime(MX1,true);
int init[](){is_prime[1]false;for(int i2;i*iMX;i){if(is_prime[i]){for(int ji*i;jMX;ji){is_prime[j]false;}}}return 0;
}();
class Solution {
public:long long countPaths(int n, vectorvectorint edges) {vectorvectorintg(n1);for(autoe:edges){int xe[0],ye[1];g[x].push_back(y);g[y].push_back(x);}//计算质数结点连接的每一个子树中的非质数结点个数vectorintsz(n1);vectorintnodes;functionvoid(int,int) dfs[](int x,int fa){nodes.push_back(x);for(int y:g[x])if(y!fa!is_prime[y])dfs(y,x);};long long ans0;for(int x1;xn;x){if(!is_prime[x]) continue;int sum0;for(int y:g[x]){if(is_prime[y]) continue;if(sz[y]0){nodes.clear();dfs(y,-1);for(int z:nodes){sz[z]nodes.size();}} ans(long long)sum*sz[y];//以i为中间点的路径sumsz[y];}anssum;//以i为端点的路径}return ans;}
};
