Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
有一堆石子,每次取其中最大重量的两颗,若重量一样,则两颗都消失,否则其中一颗消失,另一颗重量变为两者重量之差,问最后剩下的石头重量多少,用priority queue直接模拟即可


 1 #1046
 2 #Runtime: 29 ms (Beats 83.46%)
 3 #Memory: 13.9 MB (Beats 47.65%)
 4 
 5 class Solution:
 6     def lastStoneWeight(self, stones: List[int]) -> int:
 7         hp = []
 8         for st in stones:
 9             heapq.heappush(hp, -st)
10         while len(hp) >= 2:
11             s1 = heapq.heappop(hp)
12             s2 = heapq.heappop(hp)
13             if s2 > s1:
14                 heapq.heappush(hp, s1 - s2)
15         return abs(hp[0]) if hp else 0

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