求教一道脸书面经题

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.    }
   
8. }
   
9. 
   
10. User copy(User u) {
    
11. // implementation here...
    
12. }

复制代码

如题，有一个user class，实现method d

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

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

ph from root node，但是可以有环，应该怎么处理？

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;
   
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

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

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

一样用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吗？  没区别啊。