网站设计师发展,iis添加网站无法访问,seo关键字优化软件,血液中心网站建设方案文章目录1. 题目2. 解题2.1 超时解2.2 二分查找1. 题目
有个马戏团正在设计叠罗汉的表演节目#xff0c;一个人要站在另一人的肩膀上。出于实际和美观的考虑#xff0c;在上面的人要比下面的人矮一点且轻一点。 已知马戏团每个人的身高和体重#xff0c;请编写代码计算叠罗…
文章目录1. 题目2. 解题2.1 超时解2.2 二分查找1. 题目
有个马戏团正在设计叠罗汉的表演节目一个人要站在另一人的肩膀上。出于实际和美观的考虑在上面的人要比下面的人矮一点且轻一点。 已知马戏团每个人的身高和体重请编写代码计算叠罗汉最多能叠几个人。
示例
输入height [65,70,56,75,60,68] weight [100,150,90,190,95,110]
输出6
解释从上往下数叠罗汉最多能叠 6 层(56,90), (60,95), (65,100), (68,110), (70,150), (75,190)提示
height.length weight.length 10000来源力扣LeetCode 链接https://leetcode-cn.com/problems/circus-tower-lcci 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
类似题目 LeetCode 354. 俄罗斯套娃信封问题最长上升子序 DP/二分查找 程序员面试金典 - 面试题 08.13. 堆箱子DP
2.1 超时解
类似于最大上升子序采用DP解法时间复杂度 O(n2)O(n^2)O(n2)看上面数据规模超时妥妥的 ( 23 / 43 个通过测试用例 )
class Solution {
public:int bestSeqAtIndex(vectorint height, vectorint weight) {int i, j, n height.size(),maxP 1;vectorvectorint p(n);for(i 0; i n; i)p[i] {height[i], weight[i]};sort(p.begin(),p.end());//按身高升序vectorint dp(n,1);for(i 1; i n; i){for(j i-1; j 0; --j){if(p[i][1] p[j][1]){dp[i] max(dp[i], 1dp[j]);maxP max(maxP, dp[i]);}}}sort(p.begin(),p.end(),[](auto a, auto b){return a[1] b[1];});//按体重升序vectorint dp1(n,1);for(i 1; i n; i){for(j i-1; j 0; --j){if(p[i][0] p[j][0]){dp1[i] max(dp1[i], 1dp1[j]);maxP max(maxP, dp1[i]);}}}return maxP;}
};2.2 二分查找
思路对一个变量排序第一个变量相等的时候第二个变量降序排列一会求第二个变量的最长上升子序避免第一个变量相等也取进去然后dp[i] 表示长度为 i 的上升子序的 序列最后一个数的最小值采用二分查找找到第一个大于等于 target 的
class Solution {
public:int bestSeqAtIndex(vectorint height, vectorint weight) {int i, idx0, n height.size();vectorpairint,int p(n);for(i 0; i n; i)p[i] {height[i], weight[i]};sort(p.begin(),p.end(),[](auto a, auto b){if(a.firstb.first)return a.second b.second;//升高一样降序避免选择上升子序时把他们同时选上return a.first b.first;});//按身高升序vectorint dp(n);for(i 0; i n; i){auto it lower_bound(dp.begin(),dp.begin()idx,p[i].second);//二分查找求体重的最长上升子序*it p[i].second;if(it-dp.begin()idx)idx;}return idx;}
};404 ms 46.3 MB
自己编写二分查找
class Solution {
public:int bestSeqAtIndex(vectorint height, vectorint weight) {int i, j, len1, n height.size();vectorpairint,int p(n);for(i 0; i n; i)p[i] {height[i], weight[i]};sort(p.begin(),p.end(),[](auto a, auto b){if(a.firstb.first)return a.second b.second;//升高一样降序避免选择上升子序时把他们同时选上return a.first b.first;});//按身高升序vectorint dp(n);dp[0] p[0].second;for(i 1; i n; i){j bs(dp,0,len-1,len,p[i].second);//二分查找求体重的最长上升子序dp[j] p[i].second;if(j len)len;}return len;}int bs(vectorint dp, int l, int r, int len, int target){ //第一个 大于等于 我的int mid;while(l r){mid l((r-l)1);if(dp[mid] target){if(mid0 || dp[mid-1] target)return mid;elser mid-1;}else// if(dp[mid] target)l mid1;}return len;//没有找打说明它是最大的}
};264 ms 46.5 MB
