Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出每个人的体重people[i]和小船的载客量limit,每次最多搭载两个人,问最少要几艘船可以运送完所有人,保证人的最大体重不超过载客量
贪心,先对people排序,然后两个游标从左到右,若两者相加超过载客量,则这艘船只搭载右指针重的那个人,右指针向中间移动,否则搭载这两个人,左右指针都向中间移动


 1 #881
 2 #Runtime: 384 ms (Beats 53.98%)
 3 #Memory: 18.9 MB (Beats 18.14%)
 4 
 5 class Solution(object):
 6     def numRescueBoats(self, people, limit):
 7         """
 8         :type people: List[int]
 9         :type limit: int
10         :rtype: int
11         """
12         people.sort()
13         p1 = 0
14         p2 = len(people) - 1
15         ans = 0
16         while p1 <= p2:
17             if p1 == p2:
18                 ans += 1
19                 break
20             if people[p1] + people[p2] <= limit:
21                 ans += 1
22                 p1 += 1
23                 p2 -= 1
24             else:
25                 ans += 1
26                 p2 -= 1
27         return ans
28 

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理