leetcode:面试题 17.07. 婴儿名字(并查集,代码超时了)

    技术2022-07-11  86

    题目:

    分析:

    并查集。 我用python写的, 1.创建一个二维列表,然后每个列表中的元素都只有一个,为每个名字。 2.查synonyms,匹配的名字对应的列表合并。 3.排序,求和。

    竟然超时了,这道题拖了10天,答案也不好,放弃了。

    代码:

    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]: # 首先为每一个名字创建一个列表 m = {} l2 = [[]for i in range(len(names))] for i in range(len(names)): s = names[i].split('(') # 添加的是单个的元素 names.append(s[0]) m[s[0]] = int(s[1][1:len(s[1])]) for i in range(len(synonyms)): s = synonyms[i].split(',') s1 = s[0][1:len(s[0])] s2 = s[1][0:len(s[0])-1] n1 = -1 n2 = -1 for x in range(len(l2)): if s1 in l2[x]: n1=x break for x in range(len(l2)): if s2 in l2[x]: n2=x break if n1 == n2 or n1 == -1 or n2 == -1: continue l2[n1].extend(l2[n2]) del l2[n2] ll = [] for i in range(len(l2)): s = l2[i][0] all1 = 0 for j in range(len(l2[i])): all1 = all1+m[l2[i][j]] if s < l2[i][j]: s = l2[i][j] s2 = s+'('+str(all1)+')' ll.append(s2) return ll
    Processed: 0.017, SQL: 9