Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出一堆石子的重量,分到k个包里,每个包需要i~j连续堆全部取完,每堆的cost为weights[i]+weights[j],求不同的分配方式里面k堆的总cost最大值和最小值之差
思路参考 -> https://leetcode.com/problems/put-marbles-in-bags/solutions/3734284/sort-video-solution/


 1 #2551
 2 #Runtime: 758 ms (Beats 16.67%)
 3 #Memory: 25.1 MB (Beats 16.67%)
 4 
 5 class Solution(object):
 6     def putMarbles(self, weights, k):
 7         """
 8         :type weights: List[int]
 9         :type k: int
10         :rtype: int
11         """
12         n = len(weights)
13         p = [0] * (n - 1)
14         for i in range(1, n):
15             p[i - 1] = weights[i] + weights[i - 1]
16         p.sort()
17         minx, maxx = 0, 0
18         for i in range(k - 1):
19             minx += p[i]
20             maxx += p[n - i - 2]
21         return maxx - minx

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