G店面

1. sorting the linked list
2. There are sticks with various lengths in a bo

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

to connect all of the sticks in a box.  

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

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

第二题的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]))

复制代码

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

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

新人求各位支持点大米！

第二题电面老哥有啥思路吗？新手没想到啥好想法

xiana406 发表于 2019/04/28 12:00:29
第二题电面老哥有啥思路吗？新手没想到啥好想法

如果是一个数组的形式的话就嗣衣领的包装吧，最优二分法也可以用DP

补充内容 (2019-4-28 12:53):
等等，我读错了，题目不一样，不过应该还是DP

Pq 然后每次都选两个最小的？

第二題不用連續的話就greedy吧

楼主第二题没给个总长度限制条件吗？
如果只是把所有stick都连上那先连哪两个都一样啊
最后的总cost就是所有stick长度之和

orbiak 发表于 2019/04/28 21:02:59


不一樣啊...
e.g. 1, 3, 4
最佳策略是先挑1,3 再挑4
總和=(1+3)+(4+4)=12

如果先挑3,4
會變成 (3+4)+(1+7)=15

哦哦 我理解错了题意 连上还放回
那greedy能做 用pq

我就问一句 你们都在一个小时里把代码写出来的吗？我觉得来不及写完啊 一题就要一小时了