新鲜店面骨狗

第一次发帖，感觉跪了，发了一个simpson家谱的题目来，问我找两个node的edge数量，因为是家谱所以不是树形结构，这个问题

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

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

度信息，最后找到共同ancestor之后两个深度之和就是结果。。。

stella落尘 发表于 2017-12-14 10:53
祝楼主好运 我想请问为什么bart到selma的edge距离是3？  Homer Marge 是一个人么

不能发图那我就画一个吧：
       Abe Mona                   Clancy Jacquin
   /.          \.                 /             |.          \
Herb       Homer      Marge       Patty       Selma
          /.    |    \                                         \
       Bart Lisa  Maggie                              Ling

用BFS找圖的最短路徑
我假設夫妻之間的距離為0
並把夫妻當成一個 node 來看
也就是說原本 Abe 和 Mona 在圖中應該是兩個不同的 node，但我把他們用同個 node 來代表，此 node 命名為 abeMona

1. import java.util.*;
   
2. public class Simpson {
   
3.     public static void main(String[] args){
   
4.         Map<PersonNode,Set<PersonNode>> familyTree = new HashMap<>();
   
5. 
   
6.         PersonNode abe = new PersonNode("Abe");
   
7.         familyTree.put(abe,new HashSet<>());
   
8. 
   
9.         PersonNode mona = new PersonNode("Mona");
   
10.         familyTree.put(mona,new HashSet<>());
    
11. 
    
12.         PersonNode clancy = new PersonNode("Clancy");
    
13.         familyTree.put(clancy,new HashSet<>());
    
14. 
    
15.         PersonNode jacqueline = new PersonNode("Jacqueline");
    
16.         familyTree.put(jacqueline,new HashSet<>());
    
17. 
    
18.         PersonNode herb = new PersonNode("Herb");
    
19.         familyTree.put(herb,new HashSet<>());
    
20. 
    
21.         PersonNode homer = new PersonNode("Homer");
    
22.         familyTree.put(homer,new HashSet<>());
    
23. 
    
24.         PersonNode marge = new PersonNode("Marge");
    
25.         familyTree.put(marge,new HashSet<>());
    
26. 
    
27.         PersonNode patty = new PersonNode("Patty");
    
28.         familyTree.put(patty,new HashSet<>());
    
29. 
    
30.         PersonNode selma = new PersonNode("Selma");
    
31.         familyTree.put(selma,new HashSet<>());
    
32. 
    
33.         PersonNode bart = new PersonNode("Bart");
    
34.         familyTree.put(bart,new HashSet<>());
    
35. 
    
36.         PersonNode lisa = new PersonNode("Lisa");
    
37.         familyTree.put(lisa,new HashSet<>());
    
38. 
    
39.         PersonNode maggie = new PersonNode("Maggie");
    
40.         familyTree.put(maggie,new HashSet<>());
    
41. 
    
42.         PersonNode ling = new PersonNode("Ling");
    
43.         familyTree.put(ling,new HashSet<>());
    
44. 
    
45. 
    
46. 
    
47.         /*We view couple as one single node*/
    
48.         PersonNode abeMona = new PersonNode("AbeMona");
    
49.         familyTree.put(abeMona,new HashSet<>());
    
50. 
    
51.         PersonNode clancyJacqueline = new PersonNode("ClancyJacqueline");
    
52.         familyTree.put(clancyJacqueline,new HashSet<>());
    
53. 
    
54.         PersonNode homerMarge = new PersonNode("HoerMarge");
    
55.         familyTree.put(homerMarge,new HashSet<>());
    
56. 
    
57. 
    
58.         /*construct edges*/
    
59.         familyTree.get(abeMona).add(herb);
    
60.         familyTree.get(abeMona).add(homerMarge);
    
61. 
    
62.         familyTree.get(clancyJacqueline).add(homerMarge);
    
63.         familyTree.get(clancyJacqueline).add(patty);
    
64.         familyTree.get(clancyJacqueline).add(selma);
    
65. 
    
66.         familyTree.get(herb).add(abeMona);
    
67. 
    
68.         familyTree.get(homerMarge).add(abeMona);
    
69.         familyTree.get(homerMarge).add(clancyJacqueline);
    
70.         familyTree.get(homerMarge).add(bart);
    
71.         familyTree.get(homerMarge).add(lisa);
    
72.         familyTree.get(homerMarge).add(maggie);
    
73. 
    
74.         familyTree.get(patty).add(clancyJacqueline);
    
75. 
    
76.         familyTree.get(selma).add(clancyJacqueline);
    
77.         familyTree.get(selma).add(ling);
    
78. 
    
79.         familyTree.get(bart).add(homerMarge);
    
80. 
    
81.         familyTree.get(lisa).add(homerMarge);
    
82. 
    
83.         familyTree.get(maggie).add(homerMarge);
    
84. 
    
85.         familyTree.get(ling).add(selma);
    
86. 
    
87. 
    
88. 
    
89.         /*If someone is married, put that person and his/her spouse into this map*/
    
90.         HashMap<PersonNode,PersonNode> couple = new HashMap<>();
    
91. 
    
92.         couple.put(abe,abeMona);
    
93.         couple.put(mona,abeMona);
    
94. 
    
95.         couple.put(clancy,clancyJacqueline);
    
96.         couple.put(jacqueline,clancyJacqueline);
    
97. 
    
98.         couple.put(homer,homerMarge);
    
99.         couple.put(marge,homerMarge);
    
100. 
     
101. 
     
102.         Simpson s = new Simpson();
     
103.         int distance = s.findShortestDistance(abe,mona, familyTree,couple);
     
104.         System.out.println(distance);
     
105.     }
     
106. 
     
107.     int findShortestDistance(PersonNode A, PersonNode B, Map<PersonNode,Set<PersonNode>> familyTree, HashMap<PersonNode,PersonNode> couple){
     
108.         //if person A and person B are couple, return 0;
     
109.         if(couple.containsKey(A) && couple.containsKey(B) && couple.get(A).equals(couple.get(B)))
     
110.             return 0;
     
111.         //if person A is married but B is not his/her spouse, we use A's spouse to search instead of A
     
112.         if(couple.containsKey(A))
     
113.             A = couple.get(A);
     
114. 
     
115.         //if person B is married but A is not his/her spouse, we use B's spouse to search instead of B
     
116.         if(couple.containsKey(B))
     
117.             B = couple.get(B);
     
118.         Queue<PersonNode> myQ = new LinkedList<>();
     
119.         Set<PersonNode> visited = new HashSet<>();
     
120.         int distance = 0;
     
121.         myQ.add(A);
     
122.         visited.add(A);
     
123. 
     
124.         while(!myQ.isEmpty()){
     
125.             int qSize = myQ.size();
     
126.             for(int i=0; i<qSize; i++){
     
127.                 PersonNode curPerson = myQ.poll();
     
128.                 if(curPerson == B)
     
129.                     return distance;
     
130. 
     
131.                 for(PersonNode p : familyTree.get(curPerson)){
     
132.                     if(!visited.contains(p)){
     
133.                         myQ.add(p);
     
134.                         visited.add(curPerson);
     
135.                     }
     
136.                 }
     
137.             }
     
138.             distance++;
     
139.         }
     
140.         //we cannot find a path from A to B
     
141.         return -1;
     
142.     }
     
143. }
     
144. 
     
145. class PersonNode{
     
146.     String name;
     
147.     PersonNode(String name){
     
148.         this.name = name;
     
149.     }
     
150. 
     
151.     public boolean equals(Object o){
     
152.         PersonNode p = (PersonNode) o;
     
153.         return this.name.equals(p.name);
     
154.     }
     
155. 
     
156.     public int hashCode(){
     
157.         return name.hashCode();
     
158.     }
     
159. }
     
160. 
     
161. 
     

复制代码

所以tree root是連到Abe 和 Clancy嗎？

祝楼主好运 我想请问为什么bart到selma的edge距离是3？  Homer Marge 是一个人么

b01501085 发表于 2017-12-14 08:28
所以tree root是連到Abe 和 Clancy嗎？

层主，你搜下simpson family tree就可以了，他俩是亲家

b01501085 发表于 2017-12-14 08:28
所以tree root是連到Abe 和 Clancy嗎？

Abe 和 Mona 是夫妻， Clancy 和 Jacquin是夫妻，抱歉图画的不太好， Homer和Marge是夫妻，其他都是单身

stella落尘 发表于 2017-12-14 10:53
祝楼主好运 我想请问为什么bart到selma的edge距离是3？  Homer Marge 是一个人么

不好意思图画的很垃圾，呜呜，，，那个原图是bart的妈妈是Magie 然后Magie妈妈是Jacquin，所以Bart到Jacquin，两层，然后下来一层到Selma就三个边了

学习受教了， 羡慕LZ的思路

chengrr 发表于 2017-12-14 12:42

谢谢！明白了！祝楼主面试成功！