leetcode面試題 17.08. 馬戲團人塔(二分法)

有個馬戲團正在設計疊羅漢的表演節目,一個人要站在另一人的肩膀上。出于實際和美觀的考慮,在上面的人要比下面的人矮一點且輕一點。已知馬戲團每個人的身高和體重,請編寫代碼計算疊羅漢最多能疊幾個人。

示例:

輸入: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)

class Solution {int[] dp;public int bestSeqAtIndex(int[] height, int[] weight) {int n=height.length;int[][] com=new int[n][2];for(int c=0;c<n;c++){com[c][0]=height[c];com[c][1]=weight[c];}Arrays.sort(com,(o1, o2) -> o1[0]==o2[0]?o2[1]-o1[1]:o1[0]-o2[0]);//身高升序,體重降序dp=new int[n];int res=0;dp[res]=com[0][1];res++;for(int i=1;i<n;i++)if(com[i][1]>dp[res-1]) dp[res++]=com[i][1];else {int l=0,r=res-1;//在已經選擇了的體重中,找出當前體重應該放置的位置while (l<=r){int mid=(r-l)/2+l;if(dp[mid]>=com[i][1])r=mid-1;else l=mid+1;}dp[l]=com[i][1];}return res;}
}

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/393484.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/393484.shtml
英文地址,請注明出處:http://en.pswp.cn/news/393484.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

如何選擇適合自己的CMS建站系統

如今做網站已不像過去那樣必須找網站公司才能建&#xff0c;因為網上針對建站的各種CMS建站系統層出不窮。像PageAdmin、DEDECMS、帝國CMS、Discuz等&#xff0c;這些CMS系統各有各的特點和優勢&#xff0c;小熊優化的小編我從事網站制作和網站優化多年&#xff0c;和很多建站朋…

python dict hash算法_2020年3月26日python學習筆記——hash

什么是哈希&#xff1f;hash,一般翻譯做散列、雜湊&#xff0c;或音譯為哈希&#xff0c;是把任意長度的輸入(又叫做預映射pre-image)通過散列算法變換成固定長度的輸出&#xff0c;該輸出就是散列值。這種轉換是一種壓縮映射&#xff0c;也就是&#xff0c;散列值的空間通常遠…

數據處理不等式:Data Processing Inequality

我是在差分隱私下看到的&#xff0c;新解決方案的可用性肯定小于原有解決方案的可用性&#xff0c;也就是說信息的后續處理只會降低所擁有的信息量。 那么如果這么說的話為什么還要做特征工程呢&#xff0c;這是因為該不等式有一個巨大的前提就是數據處理方法無比的強大&#x…

aws架構_如何使用AWS構建可擴展架構

aws架構What I learned building the StateOfVeganism ?我學到的建立素食主義的方法是什么&#xff1f; By now, we all know that news and media shape our views on the topics we discuss. Of course, this is different from person to person. Some might be influence…

gulp 實現sass自動化 ,監聽同步

實現功能 監聽scss文件   sass自動化 準備條件 1 .安裝gulp npm init ---->一直enter&#xff0c;會在當前目錄下生成一個package.json文件,記錄安裝的依賴模塊 npm install gulp --save-dev 2 .安裝gulp-ruby-sass npm install gulp-ruby-sass 你還需要安裝ruby環境…

leetcode面試題 10.03. 搜索旋轉數組(二分法)

搜索旋轉數組。給定一個排序后的數組&#xff0c;包含n個整數&#xff0c;但這個數組已被旋轉過很多次了&#xff0c;次數不詳。請編寫代碼找出數組中的某個元素&#xff0c;假設數組元素原先是按升序排列的。若有多個相同元素&#xff0c;返回索引值最小的一個。 示例1: 輸入…

MSSQL → 02:數據庫結構

一、數據庫的組成 在SQL Server 2008中&#xff0c;用戶如何訪問及使用數據庫&#xff0c;就需要正確了解數據庫中所有對象及其設置。數據庫就像一個容器&#xff0c;它里面除了存放著數據的表之外&#xff0c;還有視圖、存儲過程、觸發器、約束等數據庫對象。數據庫管理的核心…

JAVA拳皇_拳皇(Java簡單的小程序)代碼實例|chu

剛開始學習Java&#xff0c;看完老九君的視頻根據他的內容敲的代碼&#xff0c;感覺還挺有成就感的&#xff0c;畢竟剛學習Java。package helloasd;import java.util.*; public class hellojava { public static void main(String[] args) { Scanner input new Scanner(System…

mySQL教程 第9章 觸發器

第9章 觸發器 入的新數據放到new表&#xff0c;刪除的數據放到old表。 準備本章學習環境 連接數據庫schoolDB&#xff0c;刪除表TStudent&#xff0c;TScore和Tsubject中的所有數據。 delete from TStudent; delete from TScore; delete from TSubject; 向學生表插入兩條記錄 i…

vue使用python_如何使用Python和Vue創建兩人游戲

vue使用pythonby Neo Ighodaro由新Ighodaro 如何使用Python和Vue創建兩人游戲 (How to create a two-player game with Python and Vue) In this tutorial, we will create a realtime tic-tac-toe game using Python and Pusher channels. Here’s a demo of how the game wi…

掩碼圖制作photoshop__新手用

1.首先你得有一張圖&#xff0c;比如這樣的&#xff1a; 2.用PS打開他 3.左邊工具欄里&#xff08;快速選擇工具W&#xff09;&#xff0c;選想顯示的部分 4.ctrlc復制一下&#xff0c;新建一張黑底圖粘貼上去或者白底圖時選中顯示區即花瓣右鍵反向右鍵填充成黑色 5.菜單欄->…

leetcode287. 尋找重復數(二分法)

給定一個包含 n 1 個整數的數組 nums&#xff0c;其數字都在 1 到 n 之間&#xff08;包括 1 和 n&#xff09;&#xff0c;可知至少存在一個重復的整數。假設只有一個重復的整數&#xff0c;找出這個重復的數。 示例 1: 輸入: [1,3,4,2,2] 輸出: 2 代碼 class Solution {…

os-enviroment

pip3 install PyUserInput ping 是不帶協議的轉載于:https://www.cnblogs.com/liuweimingcprogram/p/10957592.html

java 壓縮 亂碼_如何解決java壓縮文件亂碼問題

用java來打包文件生成壓縮文件&#xff0c;有兩個地方會出現亂碼&#xff1a;內容的中文亂碼問題&#xff1a;修改sun的源碼。使用開源的類庫org.apache.tools.zip.ZipOutputStream和org.apache.tools.zip.ZipEntry&#xff0c;這兩個類ant.jar中有&#xff0c;可以下載使用即可…

Unity3D手機斗地主游戲開發實戰(02)_叫地主功能實現

大體思路 前面我們實現了點擊開始游戲按鈕&#xff0c;系統依次給玩家發牌的邏輯和動畫&#xff0c;并展示當前的手牌。這期我們繼續實現接下來的功能--叫地主。 1.首先這兩天&#xff0c;學習了DOTween&#xff0c;這是一個強大的Unity動畫插件&#xff0c;大家可以參考&#…

TensorFlow 學習(十)—— 工具函數

1. 基本 tf.clip_by_value() 截斷&#xff0c;常和對數函數結合使用 # 計算交叉熵crose_ent -tf.reduce_mean(tf.log(y_*tf.clip_by_value(y, 1e-10, 1.))) a tf.reshape(tf.range(6, dtypetf.float32), [2, 3]) tf.clip_by_value(a, 2.5, 4.5) # 將值限定在 2.5 …

delphi5開發人員指南_非設計人員的網頁設計開發人員指南

delphi5開發人員指南I created my first website as a school project when I was 14. The task was simple: create a very basic site including some text, images, and a table. My usual attitude to school projects was to completely forget about them and later come…

leetcode1292. 元素和小于等于閾值的正方形的最大邊長(二分法+前綴和)

給你一個大小為 m x n 的矩陣 mat 和一個整數閾值 threshold。 請你返回元素總和小于或等于閾值的正方形區域的最大邊長&#xff1b;如果沒有這樣的正方形區域&#xff0c;則返回 0 。 示例 2&#xff1a; 輸入&#xff1a;mat [[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2…

java 反射 獲取成員_java 反射獲取成員

package com.wxjaa; import java.lang.reflect.Constructor; import java.lang.reflect.Field; import java.lang.reflect.Method; public class TestReflect { public static void main(String[] args) throws Exception { // getDeclaredField 可以獲取私有成員&#xff0c; …

Koa 中實現 chunked 數據傳輸

有關于 Transfer-Encoding:chunked 類型的響應&#xff0c;參見之前的文章HTTP 響應的分塊傳輸。這里看 Koa 中如何實現。 Koa 中請求返回的處理 雖然官方文檔有描述說明不建議直接調用 response.write&#xff1a; Bypassing Koas response handling is not supported. Avoid …