R3-图篇

饭前一道题

思路：

单向构造

 

python">class Solution:def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:m=n=len(adjacentPairs)#n表示数组元素总数n+=1#统计dict=defaultdict(int)#存储关系哈希表hashmap=defaultdict(list)for a,b in adjacentPairs:dict[a]+=1dict[b]+=1hashmap[a].append(b)hashmap[b].append(a)#数组开始的元素start=-1for i,v in dict.items():if v==1:start = ibreakret=[0]*nret[0]=startret[1]=hashmap[start][0]for i in range(2,n):x=ret[i-1]for j in hashmap[x]:if j!=ret[i-2]:ret[i]=jreturn ret

 ps:也能用双向构造（双指针法）---任取一个元素放在nums，然后两边遍历