首页 > 代码库 > How to find friends
How to find friends
How to find friends
思路简单,编码不易
1 def check_connection(network, first, second): 2 link_dictionary = dict() 3 4 for link in network: 5 drones = link.split(‘-‘) 6 7 link_dictionary.setdefault(drones[0], []).append(drones[1]) 8 link_dictionary.setdefault(drones[1], []).append(drones[0]) 9 10 future = []11 visited = []12 future.append(first)13 14 while future:15 current = future.pop()16 visited.append(current)17 18 extend = link_dictionary[current]19 20 if second in extend:21 return True22 23 for each in extend:24 if each not in visited:25 future.append(each)26 27 return False使用dict存储每个人的直接关系, 如{lyly : [lala, gege]}; 使用两个list, 其中一个表示已遍历过的人, 另一个表示即将遍历的人;
另外python中的二维数组可以这么定义: connection = [[False for col in range(5)] for row in range(5)], 即一个5*5的数组, 原先尝试过这么定义error = [[False] * 5] * 5, 发现只要修改了
error[0][0], 那么error[1][0], error[2][0] ...都修改了, 因为[False] * 5产生了一个一维数组, 而外面的*5只是产生了5个引用因此, 无论修改哪一个其余的均会改变.
观摩下大神的代码
1 def check_connection(network, first, second): 2 setlist = [] 3 for connection in network: 4 s = ab = set(connection.split(‘-‘)) 5 # unify all set related to a, b 6 for t in setlist[:]: # we need to use copy 7 if t & ab: # check t include a, b 8 s |= t 9 setlist.remove(t)10 setlist.append(s) # only s include a, b11 12 return any(set([first, second]) <= s for s in setlist)将每条关系作为set, 若关系间交集不为空, 则求关系间的并集, 即关系圈;
最后查看first与second是否在某个关系圈中;
充分利用了set的操作, &交, |并, <=子集;
还有第12行的语法特性
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。