滴滴算法第二题。考试完想了一下其实很简单，当时没做出来。

# 6 2 3
# 2 1
# 3 4 5 6 1
# 2 3 4 5 6
import collections
n,m,d = map(int,input().strip().split())
l = list(map(int,input().strip().split()))
w = list(map(int,input().strip().split()))
a = collections.defaultdict(int)  # child -> father
b = collections.defaultdict(int)  # father -> child

for i in range(n-1):
    a[i+2] = w[i]
    b[w[i]] = i+2
res = []
for i in range(m):
    new = [l[i]]
    level = 0
    now = l[i]
    while a[now] != 0 and level < d:
        new.append(a[now])
        level += 1
        now = a[now]
    level = 0
    now = l[i]
    while b[now] != 0  and level < d:
        new.append(b[now])
        level += 1
        now = b[now]
    if i==0:
        res.extend(new)
    else:
        res = [x for x in res if x in new]
#print(res)
print(len(res))

#滴滴##笔试题目#

全部评论

推荐最新楼层

Amphi17

香港大学算法工程师

我也后来做了下，思路应该是没什么问题，但我这个有很多重复计算。楼上的那个比我好 from collections import defaultdict n,m,d = map(int,input().split()) spec = [int(c) for c in input().split()] lis = [int(c) for c in input().split()] # nei为节点邻接表 neighbor = defaultdict(list) for i in range(n-1): neighbor[i+2].append(lis[i]) neighbor[lis[i]].append(i+2) def bfs(node0): queue=[] visited=set() queue.append(node0) visited.add(node0) dis=[0 for _ in range(n+1)] step=0 while queue: node=queue.pop() step+=1 for each in neighbor[node]: if each not in visited: queue.append(each) visited.add(each) dis[each]=step #print(queue) return dis count=0 for i in range(1,n+1): dis=0 for point in spec: dis=max(bfs(point)[i],dis) if dis<=d: count+=1 print(count)

点赞回复分享

发布于 2019-08-28 23:19

INFP_Pandas

华为_软件开发工程师

n,m,d = map(int,input().split()) spec = [int(c) for c in input().split()] lis = [int(c) for c in input().split()] # nei为节点邻接表 nei = [[] for _ in range(n+1)] for i in range(n-1): nei[i+2].append(lis[i]) nei[lis[i]].append(i+2) for i in range(1,n+1): nei[i].append(i) flag = [0] * (n+1) for i in range(m): dis = 1 queue = [spec[i]] # 存储bfs遍历的节点 see = set() while queue: size = len(queue) while size != 0 : tmp = queue.pop(0) for j in range(len(nei[tmp])): if nei[tmp][j] not in see: see.add(nei[tmp][j]) flag[nei[tmp][j]] += 1 for i in nei[tmp]: if i != tmp: queue.append(i) size -= 1 dis += 1 if dis > d: break #共有多少合适的点 count = 0 for i in range(len(flag)): if flag[i] == m: count += 1 print(count) 我觉得这题是个无向图的题，和树关系好像不大，参考了邻接表 + bfs的方法，总的思路就是： 1、以各特殊点bfs展开，当bfs深度为大于d时，切换为下一个特殊点， 2、如此往复，便记录下每个节点总共被以特殊点为起点的节点遍历到的次数 3、如果遍历次数等于特殊节点数量，即为符合要求的节点

点赞回复分享

发布于 2019-08-28 15:55

靠谱内推大哥

楼主

小红书_推荐算法工程师

我果然太菜了，把一颗树当成链表了，考虑问题有点简单。

点赞回复分享

发布于 2019-08-28 13:23

曲陌灵风

武汉大学算法工程师

你这只能通过数组上面的用例吧，然而这不是一棵树么，很明显这个数组里面会有重复数字啊，你这样建defaultdict肯定有问题啊

点赞回复分享