贝壳找房 9月7日 笔试题 第四题-查族谱

时间:2020-9-9 作者:admin

贝壳找房第四题代码,时间复杂度o(nlogn)

 

题目:

样例:

代码:

n = 4 # 结点数
pairs = [[1,2],[3,4],[3,1]] # 边
child = [-1,2,0,1,0] # 孩子数 1-n 多加了个-1为了填充index=0
query = [[1,3],[4,1],[2,4]] # 查询对

fa = list(range(0,n+1)) # 用来查找当前父亲,与并查集相同, pre[i] = i 初始化

graph = [[0]*(n+1) for _ in range(n+1)] # 边图

for x1,x2 in pairs:
    graph[x1][x2] = 1 # 把其变成无向图
    graph[x2][x1] = 1

sum1 = 0 # 用来判断当前状态
'''
这里每一次只找当前的孩子(child[i]==0)的结点,将其与之相连的点j,若还有孩子数,将其设为其父亲,
并且将父亲结点的孩子数child[j] -= 1,并将child[i] 设为-1,
如果所有结点为-1,即child和为-n,说明树设置完成,sum1是用来判断是否找完。
'''
while sum1 != -n:
    sum1 = 0
    for i in range(1,n+1):
        if child[i] == 0:
            for j in range(1,n+1):
                if graph[i][j] == 1 and child[j] > 0:
                    fa[i] = j
                    child[j] -= 1
                    break # 只会有一个父亲
            child[i] = -1
        sum1 += child[i]
'''
--------------------------------------分割线------------------------------------------
下面开始设置查询步骤,
1、findpre 找到当前结点祖先的列表,并翻转便于搜索
2、findnearpre 判断两点关系。
'''
def findpre(u):
    fathers = []
    while u != fa[u]:
        fathers.append(fa[u])
        u = fa[u]
    fathers.reverse()
    return fathers
        
def findnearpre(u, v):
    u_list = findpre(u)
    v_list = findpre(v)

    if u in v_list:
        return 'ZZZZ'
    elif v in u_list:
        return 'SSSS'
    else:
        # 查找最后相等的结点值
        for i in range(0,min(len(u_list),len(v_list))):
            if u_list[i] != v_list[i]:
                return u_list[i-1]
            else:
                cur = u_list[i]
        return cur

for u,v in query:
    print(findnearpre(u,v))
            

 

声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。