求教一道脸书面经题

1. class User {
   
2.    String name;
   
3.    List<User> friends;
   
4.    User(String name, List<User> friends) {
   
5.       this.name = name;
   
6.       this.friends = friends;
   
7.    }
   . visit 1point3acres.com for more.
8. }
   
9. 
   
10. User copy(User u) {
    
11. // implementation here...
    
12. }

复制代码

如题，有一个user class，实现method deep copy 一个 user。注意环， 例如 b 是 a friend, c 是 b friend, a 是 c friend. 代码具体应该如何实现？


补充内容 (2017-6-23 06:41):
应该就是deep copy graph from root node，但是可以有环，应该怎么处理？

关注一亩三分地公众号：
Warald_一亩三分地

1. #include <iostream>
   
2. #include <vector>
   
3. #include <unordered_map>
   
4. #include <string>
   
5. using namespace std;
   
6. class User {
   
7. public:
   
8.     string name;
   
9.     vector<User*> friends;
   . 鍥磋�傛垜浠珸1point 3 acres
10.     User(string name) {
    
11.         this->name = name;
    
12.     }
    
13. };
    
14. User *copy(User *u,unordered_map<User*, User*>& mp) {
    
15.     if(mp.count(u)) return mp[u]; // alreay grey (in dfs path) or black
    
16.    
    
17.     // color grey
    
18.     mp[u] = new User(u->name+" copy");
    
19.     for(auto x:u->friends){
    
20.         mp[u]->friends.push_back(copy(x,mp));
    
21.     }
    
22.     return mp[u];
    
23.    
    
24.     //color black
    
25. }
    
26. int main(int argc, const char * argv[]) {
    
27.     User* a = new User("a");
    
28.     User* b = new User("b");
    
29.     User* c = new User("c");
    
30.     a->friends.push_back(b);
    
31.     b->friends.push_back(c);
    
32.     c->friends.push_back(a);
    
33.     unordered_map<User*, User*> mp; // user to user copy map "a"->"a copy"
    
34.     User* a_copy = copy(a,mp);
    
35.     cout<<a_copy->name<<endl;
    
36.     cout<<a_copy->friends[0]->name<<endl;
    
37.     cout<<a_copy->friends[0]->friends[0]->name<<endl;
    
38.    
    
39.     return 0;
    
40. }
    

复制代码

a copy
b copy
c copy
Program ended with exit code: 0

关注一亩三分地微博：
Warald

一样用hash记录哪些已经copy了？

这题坑的地方是不是要重写equal和hashcode函数？

33847682 发表于 2017-6-23 06:57
这题坑的地方是不是要重写equal和hashcode函数？

我也是一头雾水，但是目前知道的信息只有这么多

edyyy 发表于 2017-6-23 06:52
一样用hash记录哪些已经copy了？

比如说你在copy a，dfs到c，发现有一个friend a，此时a 还没有entry 在map，怎么办呢？

dfs的染色可以染三种啊，白，灰，黑， 灰就代表还在dfs路径上。。你这种情况下，只要是灰，你就放着map里唄，反正也是指针。(java里是reference)

用hashmap, oldNode -> newNode, 有环（keyset里面有当前node）就continue

FightOn 发表于 2017-6-23 08:18
用hashmap, oldNode -> newNode, 有环（keyset里面有当前node）就continue

赞username，一家人 哈哈

有环不也还是 LC 上的 clone graph吗？  没区别啊。

oldman09 发表于 2017-6-23 07:01
比如说你在copy a，dfs到c，发现有一个friend a，此时a 还没有entry 在map，怎么办呢？

a的值copy完后 立刻存进hashmap，之后再去copy friends list 这样之后绕回a的时候就能发现a已经在map里了

youziwry 发表于 2017-6-27 11:58
a的值copy完后 立刻存进hashmap，之后再去copy friends list 这样之后绕回a的时候就能发现a已经在map里了

public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
    if (node == null) return null;
    if (map.containsKey(node)) return map.get(node);
    UndirectedGraphNode copy = new UndirectedGraphNode(node.label);
    map.put(node, copy);
    for (UndirectedGraphNode n : node.neighbors)
        copy.neighbors.add(cloneGraph(n));
    return copy;
}

这样就好了。仔细过一遍，环根本不是问题。

解法是不是可以参考clone graph?

感觉就可以用clone graph来解啊

deep copy graph from root node也会有circle，但是并不影响