亚麻 Amazon OA 社招 新题详解

谢谢分享！！

没太意会楼主的坑，我想到办法，一开始先假定N个城市是N个岛，然后根据已经有的道路进行合并，算算剩下多少个孤岛。然后用sort好的新路进行连接，连接一次孤岛减一次，孤岛为1的时候返回。如果所有新路都查完，孤岛数大于1则失败。这个方法可以吗

楼主后来去amz 了么？

附上我的c++ 解

1. class unionfind {
   
2. public:
   
3.         unionfind(int size) {
   
4.                 p = vector<int>(size, -1);
   
5.         }
   
6. 
   
7.         int find(int x) {
   
8.                 if (p[x] == -1)
   
9.                         return x;
   
10.                 return find(p[x]);
    
11.         }
    
12. 
    
13.         void make_union(int x, int y) {
    
14.                 int xp = find(x);
    
15.                 int yp = find(y);
    
16. 
    
17.                 if (xp != yp)
    
18.                         p[xp] = yp;
    
19. 
    
20.         }
    
21. 
    
22.         vector<int> p;
    
23. };
    
24. 
    
25. struct compare {
    
26.         bool operator() (vector<int> a, vector<int> b) {
    
27.                 return a[2] > b[2];
    
28.         }
    
29. };
    
30. 
    
31. int mst_min_cost(int n, int oldr, vector<vector<int>> &roads, vector<vector<int>> &newroad) {
    
32.         class unionfind uf(n+1);
    
33.         for (auto & it : roads)
    
34.                 uf.make_union(it[0], it[1]);
    
35. 
    
36.         priority_queue<vector<int>, vector<vector<int>>, compare> q;//min heap, min cost at top
    
37.         for (auto & it : newroad)
    
38.                 q.push(it);
    
39. 
    
40.         int res_cost = 0;
    
41.         while (!q.empty()) {
    
42.                 vector<int> cur = q.top();
    
43.                 q.pop();
    
44. 
    
45.                 int p1 = uf.find(cur[0]);
    
46.                 int p2 = uf.find(cur[1]);
    
47.                 if (p1 != p2) {
    
48.                         uf.make_union(p1, p2);
    
49.                         res_cost += cur[2];
    
50.                 }
    
51.         }
    
52. 
    
53.         for (int i = 2; i<n+1;i++) { // check connected components > 1
    
54.                 if (uf.find(i) != uf.find(i-1))
    
55.                         return -1;
    
56.         }
    
57. 
    
58.         return res_cost;
    
59. }

复制代码

很有用的信息！

这题的坑不应该是roadsAvailable list里面有环吗？

必须点赞加大米

第二题c++代码，欢迎讨论：

1. #include <iostream>
   
2. #include <queue>
   
3. #include <algorithm>
   
4. 
   
5. class Solution {
   
6.         int n;
   
7.         int *parent;
   
8. 
   
9.         void union(int x, int y){
   
10.                 int px=find(x);
    
11.                 int py=find(y);
    
12.                 if(px != py){
    
13.                         parent[px]=py;
    
14.                         n--;
    
15.                 }
    
16.         }
    
17.         int find(int x){
    
18.                 if(parent[x] == x){
    
19.                         return parent[x];
    
20.                 }
    
21.                 return find(parent[x]);
    
22.         }
    
23. 
    
24. public:
    
25.         getMinimumCostToConstruct(int numTotalAvailableCities, int numTotalAvailableRoads,
    
26.                 vector<vector<int>> roadsAvailable, int numNewRoadsConstruct, vector<vector<int>> costNewRoadsConstruct){
    
27.                 // corner case
    
28.                 if(numTotalAvailableCities < 2 || numTotalAvailableRoads >= numTotalAvailableCities-1){
    
29.                         return 0;
    
30.                 }
    
31.                 int n=numTotalAvailableCities;
    
32.                 parent=new int[n+1];
    
33.                 for(int i=0; i<n+1; i++){
    
34.                         parent[i]=i;
    
35.                 }
    
36.                 int existingRoadCount = 0;
    
37.                 int cost=0;
    
38.                 sort(roadsAvailable.begin(), roadsAvailable.end(), [](vector<int> a, vector<int> b){
    
39.                         return a[2]<b[2];
    
40.                 });
    
41.                 for(vector<int> pair: roadsAvailable) {
    
42.                         int x= pair[0];
    
43.                         int y= pair[1];
    
44.                         if(find(x) != find(y)){
    
45.                                 union(x, y);
    
46.                         }
    
47.                 }
    
48. 
    
49.                 for(auto it: costNewRoadsConstruct){
    
50.                         int x= it[0];
    
51.                         int y= it[1];
    
52.                         if(find(x) != find(y)){
    
53.                                 union(x, y);
    
54.                                 cost += it[2];
    
55.                         }
    
56.                 }
    
57.                 return n==1? cost: -1;
    
58.         }
    
59. };

复制代码

补充内容 (2019-9-25 11:28):
函数名 void union(int x, int y) 应该改为 void unionFind(int x, int y){}, 不然就重复关键字了。

楼主好人，还帮着想怎么节省大米下载资料。看了unionfind的写法，应该是参照的princeton algorithm的quick union的写法吧？简介明了。赞。