您好,登录后才能下订单哦!
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
本篇内容主要讲解“leetcode怎么解决马戏团人塔问题”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“leetcode怎么解决马戏团人塔问题”吧!
有个马戏团正在设计叠罗汉的表演节目,一个人要站在另一人的肩膀上。出于实际和美观的考虑,在上面的人要比下面的人矮一点且轻一点。已知马戏团每个人的身高和体重,请编写代码计算叠罗汉最多能叠几个人。
示例:
输入: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
解题思路
1,先按照身高升序排序
2,相同身高,按照体重降序排序
3,身高转化成了最长递增序列问题
代码实现
func bestSeqAtIndex(height []int, weight []int) int {if len(weight)<1{return 0}for i:=0;i<len(height);i++{for j:=i;j<len(height);j++{if height[i]>height[j]{height[i],height[j]=height[j],height[i]weight[i],weight[j]=weight[j],weight[i]}}}for i:=0;i<len(weight)-1;i++{j:=1for i+j<len(weight) && height[i]==height[i+j]{j++}weight=sort(weight,i,j)i+=j}var dp []intdp=append(dp,weight[0])for i:=1;i<len(weight);i++{if weight[i]>dp[len(dp)-1]{dp=append(dp,weight[i])}else{l:=0r:=len(dp)-1p:=0for l<=r{mid:=(l+r)>>1if weight[i]>dp[mid]{p=mid+1l=mid+1}else{r=mid-1}}dp[p]=weight[i]}}fmt.Println(dp)return len(dp)}func sort(a []int,s,e int)[]int{for i:=s;i<=e;i++{for j:=i;j<e;j++{if a[i]<a[j]{a[i],a[j]=a[j],a[i]}}}return a}
到此,相信大家对“leetcode怎么解决马戏团人塔问题”有了更深的了解,不妨来实际操作一番吧!这里是亿速云网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。