溫馨提示×

您好,登錄后才能下訂單哦!

密碼登錄×
登錄注冊(cè)×
其他方式登錄
點(diǎn)擊 登錄注冊(cè) 即表示同意《億速云用戶服務(wù)條款》

leetcode怎么解決馬戲團(tuán)人塔問(wèn)題

發(fā)布時(shí)間:2021-12-15 12:03:23 來(lái)源:億速云 閱讀:155 作者:iii 欄目:大數(shù)據(jù)

本篇內(nèi)容主要講解“l(fā)eetcode怎么解決馬戲團(tuán)人塔問(wèn)題”,感興趣的朋友不妨來(lái)看看。本文介紹的方法操作簡(jiǎn)單快捷,實(shí)用性強(qiáng)。下面就讓小編來(lái)帶大家學(xué)習(xí)“l(fā)eetcode怎么解決馬戲團(tuán)人塔問(wèn)題”吧!

有個(gè)馬戲團(tuán)正在設(shè)計(jì)疊羅漢的表演節(jié)目,一個(gè)人要站在另一人的肩膀上。出于實(shí)際和美觀的考慮,在上面的人要比下面的人矮一點(diǎn)且輕一點(diǎn)。已知馬戲團(tuán)每個(gè)人的身高和體重,請(qǐng)編寫代碼計(jì)算疊羅漢最多能疊幾個(gè)人。

示例:

輸入:height = [65,70,56,75,60,68] weight = [100,150,90,190,95,110]
輸出:6
解釋:從上往下數(shù),疊羅漢最多能疊 6 層:(56,90), (60,95), (65,100), (68,110), (70,150), (75,190)

提示:

  • height.length == weight.length <= 10000

解題思路

1,先按照身高升序排序

2,相同身高,按照體重降序排序

3,身高轉(zhuǎn)化成了最長(zhǎng)遞增序列問(wèn)題

代碼實(shí)現(xiàn)

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:=1      for i+j<len(weight) && height[i]==height[i+j]{          j++      }      weight=sort(weight,i,j)      i+=j   }  var dp []int  dp=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:=0          r:=len(dp)-1          p:=0          for l<=r{              mid:=(l+r)>>1              if weight[i]>dp[mid]{                 p=mid+1                 l=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}

到此,相信大家對(duì)“l(fā)eetcode怎么解決馬戲團(tuán)人塔問(wèn)題”有了更深的了解,不妨來(lái)實(shí)際操作一番吧!這里是億速云網(wǎng)站,更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢,關(guān)注我們,繼續(xù)學(xué)習(xí)!

向AI問(wèn)一下細(xì)節(jié)

免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI