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