Re: [閒聊] 每日LeetCode

作者: Rushia (みけねこ的鼻屎)   2023-04-03 23:10:42
881. Boats to Save People
給定一個陣列Poople,People[i] 表示第 i 個人的重量,我們有無限艘船且每個船
最多只能負重 limit 的重量並且最多載兩個人,返回把所有人載走的最少所需船數。
Example :
Input: people = [1,2], limit = 3
Output: 1
Explanation: 1 boat (1, 2)
Input: people = [3,2,2,1], limit = 3
Output: 3
Explanation: 3 boats (1, 2), (2) and (3)
思路:
1.因為船最多載兩個人,所以我們可以對重量貪婪,每次都讓重的人先上船,如果還可以
負重就讓最輕的人嘗試上船,這樣一來載完所有人就會是最少趟次。
2.因為要取最重和最輕的人所以我們可以先把people排序。
3.再來用雙指標表示當前要上船的人是誰,每次固定內縮右指標,如果可以負重就移動
左指標,每輪都讓趟次加一,當指標交錯時就是載完了。
Java Code:
作者: JIWP (JIWP)   2023-04-03 23:11:00
大師
作者: ZooseWu (N5)   2023-04-03 23:42:00
大師
作者: Mustafar (sense and feel)   2023-04-04 00:30:00
這幾天每日都是以前出現過的二分搜 ==

Links booklink

Contact Us: admin [ a t ] ucptt.com