leetcode 1482. 制作 m 束花所需的最少天數(二分查找)

給你一個整數數組 bloomDay,以及兩個整數 m 和 k 。

現需要制作 m 束花。制作花束時,需要使用花園中 相鄰的 k 朵花 。

花園中有 n 朵花,第 i 朵花會在 bloomDay[i] 時盛開,恰好 可以用于 一束 花中。

請你返回從花園中摘 m 束花需要等待的最少的天數。如果不能摘到 m 束花則返回 -1 。

示例 1:

輸入:bloomDay = [1,10,3,10,2], m = 3, k = 1
輸出:3
解釋:讓我們一起觀察這三天的花開過程,x 表示花開,而 _ 表示花還未開。
現在需要制作 3 束花,每束只需要 1 朵。
1 天后:[x, _, _, _, _] // 只能制作 1 束花
2 天后:[x, _, _, _, x] // 只能制作 2 束花
3 天后:[x, _, x, _, x] // 可以制作 3 束花,答案為 3
示例 2:

輸入:bloomDay = [1,10,3,10,2], m = 3, k = 2
輸出:-1
解釋:要制作 3 束花,每束需要 2 朵花,也就是一共需要 6 朵花。而花園中只有 5 朵花,無法滿足制作要求,返回 -1 。
示例 3:

輸入:bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3
輸出:12
解釋:要制作 2 束花,每束需要 3 朵。
花園在 7 天后和 12 天后的情況如下:
7 天后:[x, x, x, x, _, x, x]
可以用前 3 朵盛開的花制作第一束花。但不能使用后 3 朵盛開的花,因為它們不相鄰。
12 天后:[x, x, x, x, x, x, x]
顯然,我們可以用不同的方式制作兩束花。

解題思路

使用二分查找,查找出滿足情況的最小日期
檢查是否滿足條件:遍歷數組,如果開花日期是在限制日期前就作為有效的花朵,連續的k朵花,可作為一個有效花束,檢查可以生產花束的個數是否多于m

代碼

func minDays(bloomDay []int, m int, k int) int {n:=len(bloomDay)if n<m*k{return -1}max:=-1for _, day := range bloomDay {if day>max{max=day}}return sort.Search(max, func(days int) bool {cnt ,f:=0,0for i := 0; i < n; i++ {if bloomDay[i]>days{cnt=0}else{cnt++if cnt==k{f++cnt=0}}}return f>=m})
}

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

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

相關文章

算法訓練營 重編碼_編碼訓練營手冊:沉浸式工程程序介紹

算法訓練營 重編碼Before you spend thousands of dollars and several months of your life on a coding bootcamp, spend 30 minutes reading this handbook.在花費數千美元和一生中的幾個月時間參加編碼訓練營之前&#xff0c;請花30分鐘閱讀本手冊。 這本手冊適用于誰&…

面向Tableau開發人員的Python簡要介紹(第4部分)

用PYTHON探索數據 (EXPLORING DATA WITH PYTHON) Between data blends, joins, and wrestling with the resulting levels of detail in Tableau, managing relationships between data can be tricky.在數據混合&#xff0c;聯接以及在Tableau中產生的詳細程度之間進行搏斗之間…

bzoj 4552: [Tjoi2016Heoi2016]排序

Description 在2016年&#xff0c;佳媛姐姐喜歡上了數字序列。因而他經常研究關于序列的一些奇奇怪怪的問題&#xff0c;現在他在研究一個難題&#xff0c;需要你來幫助他。這個難題是這樣子的&#xff1a;給出一個1到n的全排列&#xff0c;現在對這個全排列序列進行m次局部排序…

oracle之 手動創建 emp 表 與 dept 表

說明&#xff1a; 有時候我們需要通用的實驗數據&#xff0c;emp表 與 dept表 但是數據庫中有沒有。 這時&#xff0c;我們可以手動創建。 -- 創建表與數據CREATE TABLE EMP(EMPNO NUMBER(4) NOT NULL, ENAME VARCHAR2(10), JOB VARCHAR2(9), MGR NUMBER(4), HIREDATE DATE, S…

深入理解InnoDB(8)—單表訪問

1. 訪問方法 MySQL把執行查詢語句的方式稱之為訪問方法或者訪問類型。 而訪問方法大致分為兩類 全表掃描索引 而進行細分的話可以分為以下幾類 &#xff08;為了方便說明&#xff0c;先建一個表&#xff09; CREATE TABLE single_table (id INT NOT NULL AUTO_INCREMENT,key…

蝙蝠俠遙控器pcb_通過蝙蝠俠從Circle到ML:第二部分

蝙蝠俠遙控器pcbView Graph查看圖 背景 (Background) Wait! Isn’t the above equation different from what we found last time? Yup, very different but still looks exactly the same or maybe a bit better. Just in case you are wondering what I am talking about, p…

camera驅動框架分析(上)

前言 camera驅動框架涉及到的知識點比較多&#xff0c;特別是camera本身的接口就有很多&#xff0c;有些是直接連接到soc的camif口上的&#xff0c;有些是通過usb接口導出的&#xff0c;如usb camera。我這里主要討論前者&#xff0c;也就是與soc直連的。我認為凡是涉及到usb的…

工程項目管理需要注意哪些問題

在社會科學技術發展和市場經濟繁榮昌盛的今天&#xff0c;為更好的滿足社會人性化的需求&#xff0c;建設施工企業在建筑施工、布局以及內部運行都給予了落實。而工程項目是建筑施工企業面向建筑市場的窗口&#xff0c;是企業建筑活動的前沿陣地&#xff0c;管理需更嚴謹。 雖說…

leetcode 872. 葉子相似的樹(dfs)

請考慮一棵二叉樹上所有的葉子&#xff0c;這些葉子的值按從左到右的順序排列形成一個 葉值序列 。 舉個例子&#xff0c;如上圖所示&#xff0c;給定一棵葉值序列為 (6, 7, 4, 9, 8) 的樹。 如果有兩棵二叉樹的葉值序列是相同&#xff0c;那么我們就認為它們是 葉相似 的。 …

探索感染了COVID-19的動物的數據

數據 (The data) With the number of cases steadily rising day by day, COVID-19 has been pretty much in the headlines of every newspaper known to man. Despite the massive amount of attention, a topic that has remained mostly untouched (some exceptions being …

Facebook哭暈在廁所,調查顯示用VR體驗社交的用戶僅為19%

美國娛樂軟件協會ESA調查顯示&#xff0c;有74%的用戶使用VR玩游戲&#xff0c;而僅有19%的用戶會用VR進行社交。 當我們說到VR社交&#xff0c;必然離不開Facebook。在剛剛結束的F8大會上&#xff0c;小扎展示了VR社交平臺Facebook Spaces測試版&#xff0c;巧的是此前也有好…

網頁自動刷新

eg1&#xff1a;<meta http-equiv”refresh” content”4” /> 間隔4秒網頁自動刷新 eg2&#xff1a;<meta http-equiv”refresh” content”8;http://www.baidu.com” /> 等待8秒自動跳轉到百度頁面轉載于:https://www.cnblogs.com/zwtqf/p/7667774.html

解決Javascript疲勞的方法-以及其他所有疲勞

Learn your fundamentals, and never worry again. 了解您的基礎知識&#xff0c;再也不用擔心。 新工具讓我擔心 (New Tools Worry Me) When JavaScripts shiny tool of the day comes out, I sometimes overreact. 當JavaScript一天一度的閃亮工具問世時&#xff0c;我有時R…

Java 8 的List<V> 轉成 Map<K, V>

問題&#xff1a; Java 8 的List 轉成 Map<K, V> 我想要使用Java 8的streams和lambdas轉換一個 List 對象為 Map 下面是我在Java 7里面的寫法 private Map<String, Choice> nameMap(List<Choice> choices) {final Map<String, Choice> hashMap new…

已知兩點坐標拾取怎么操作_已知的操作員學習-第4部分

已知兩點坐標拾取怎么操作有關深層學習的FAU講義 (FAU LECTURE NOTES ON DEEP LEARNING) These are the lecture notes for FAU’s YouTube Lecture “Deep Learning”. This is a full transcript of the lecture video & matching slides. We hope, you enjoy this as mu…

北京供銷大數據集團發布SinoBBD Cloud 一體化推動產業云發展

9月5日&#xff0c;第五屆全球云計算大會在上海世博展覽館盛大開幕&#xff0c;國內外頂尖企業匯聚一堂&#xff0c;新一代云計算技術產品紛紛亮相。作為國內領先的互聯網基礎服務提供商&#xff0c;北京供銷大數據集團(以下簡稱“SinoBBD”)受邀參加此次大會&#xff0c;并正式…

windows下有趣的小玩意

1.顯示文件和隱藏文件。在當前目錄下shift右鍵 選擇cmd命令 運行顯示文件: attrib -s -h 文件名 隱藏文件: attrib -s h 文件名 2.查看電腦支持的最大內存 在cmd下運行wmic memphysical get maxcapacity所得結果單位mb 所得/1024/1024 得到單位G 3.windowsR 輸入…

rxjs angular_Angular RxJS深度

rxjs angularIn this tutorial, well learn to use the RxJS 6 library with Angular 6 or Angular 7. Well learn about:在本教程中&#xff0c;我們將學習將RxJS 6庫與Angular 6或Angular 7結合使用。我們將了解&#xff1a; How to import the Observable class and the ot…

HashMap, LinkedHashMap 和 TreeMap的區別

HashMap, LinkedHashMap 和 TreeMap的區別 Java里面的HashMap, LinkedHashMap 和 TreeMap 有什么區別?我看不出以下3個key和value有什么不同的。Hashtables里面又是怎么樣的呢&#xff1f; Map m1 new HashMap(); m1.put("map", "HashMap"); m1.put(&q…

“陪護機器人”研報:距離真正“陪護”還差那么一點

一款有“缺陷”的機器人&#xff0c;怎能做到真正的“陪護”&#xff1f; 近日&#xff0c;鼎盛智能發布了一款名為Ibotn的&#xff08;愛蹦&#xff09;幼兒陪伴機器人&#xff0c;核心看點就是通過人臉識別、場景識別等計算機視覺技術來實現機器人對兒童的陪護。不過&#xf…