G店面

标题是不是写错了？是电面不是店面吧。

第二题的Python实现，很简单，供初学者参考：

1. from heapq import heapify, heappush, heappop
   
2. class Solution:
   
3. 
   
4.     def connect_sticks(self, sticks):
   
5. 
   
6.         if not sticks: return 0
   
7.         
   
8.         total_cost = 0
   
9.         heapify(sticks)
   
10.         
    
11.         while len(sticks) > 1:
    
12.             stick1 = heappop(sticks)
    
13.             stick2 = heappop(sticks)
    
14. 
    
15.             total_cost += (stick1 + stick2)
    
16. 
    
17.             heappush(sticks, stick1+stick2)
    
18.         
    
19.         return total_cost
    
20. 
    
21. if __name__ == "__main__":
    
22.     print(Solution().connect_sticks([1]))
    
23.     print(Solution().connect_sticks([1,3,4]))

复制代码

第2题如果没啥要求的话应该就是用个优先队列每次取2个最短的合并。

Wyf2222 发表于 2019-4-28 00:09
Pq 然后每次都选两个最小的？

我也是这么想的，一个简单的证明思路不知道对不对，就是假设一共n段，那么需要连接n-1次，第一次连接的两段会加n-1次，第二次连接加进去的那段n-2次，所以要让总和最小，就从最短的开始

第二题这个贪心算法证明起来还是不太容易 我没想明白 跟哈夫曼编码的原理很像

题二不是最小生成树吗？

厉害厉害