题目描述
判断是否序列 org 能唯一地由 seqs 重构得出，org是一个由从1到n的正整数排列而成的序列， 1 ≤ n ≤ 10^4 。
重构表示组合成 seqs 的一个最短的父序列 (意思是，一个最短的序列使得所有 seqs 里的序列都是它的子序列)。
判断是否有且仅有一个能从 seqs 重构出来的序列，并且这个序列是 org。
测试样例
输入:org = [1,2,3], seqs = [[1,2],[1,3]]
输出: false
解释:
[1,2,3] 并不是唯一可以被重构出的序列，还可以重构出 [1,3,2]
输入: org = [1,2,3], seqs = [[1,2]]
输出: false
解释:
能重构出的序列只有 [1,2].
输入: org = [1,2,3], seqs = [[1,2],[1,3],[2,3]]
输出: true
解释:
序列 [1,2], [1,3], 和 [2,3] 可以唯一重构出 [1,2,3].
输入:org = [4,1,5,2,6,3], seqs = [[5,2,6,3],[4,1,5,2]]
输出:true
题意理解&思路
> seqs 中的每个序列相当于图中的一条有向边；
> 由 seqs 中所有序列构成的树，每层节点数必须为1，否则这些序列就不止构成唯一序列（而是有多个）；
> seqs 中的元素需和 org 完全一致
由于最终目标是 org，因此基于 org 中的元素来构建目标图节点，根据 seqs 中的序列，构建每个点的邻居，同时计算每个点的入度。
邻居构建和入度计算完毕，便可以使用 BFS，每次取入度为0的节点用于构建序列，同时更新它邻居的入度。若有某次入度为0的节点数不止1个，则说明 seqs 可构成多个序列，目标不成立。
最终判断构建出来的序列和 org 是否一致。
具体方法
I. 以 org 中的元素为 key 初始化2个 dict，分别用于存储邻居表和入度；
II. 初始化一个空集，存储 seqs 中不同的元素，用于在处理 seqs 中的每个序列时判断是否出现了 org 以外的元素。若是，则目标不成立；
III. 遍历 seqs 中每个序列的元素，在当前元素的邻居表中加入邻居，邻居为其后的一个元素，同时为这个邻居的入度加1；
IV. 待 seqs 中所有序列均处理完毕后，判断 org 中的元素与存储 seqs 中元素的集合是否完全一致，若不是，则目标不成立；
V. 每次取入度为0的元素，若这样的元素多余1个，则目标不成立；否则，将其加入列表构建序列；
VI. 更新取出元素的邻居的入度，将它们的入度减一，然后把这些邻居加入队列；
VII. 重复V、VI直至队列为空；
VIII. 判断构建出的序列与 org 是否完全一致
代码
from collections import deque
class Solution:
"""
@param org: a permutation of the integers from 1 to n
@param seqs: a list of sequences
@return: true if it can be reconstructed only one or false
"""
def sequenceReconstruction(self, org, seqs):
# write your code here
if not org:
return True
if not seqs or not any(seqs):
return False
# 构建图，入度和邻居
indegree = {}.fromkeys(org, 0)
neighbors = {n: [] for n in org}
# 存放节点的集合，用于判断seqs中的节点和org是否完全一样
nodes = set()
for seq in seqs:
nodes.update(seq)
# 判断seqs中是否有org以外的节点
if not nodes.issubset(org):
return False
for i in range(len(seq) - 1):
indegree[seq[i+1]] += 1
neighbors[seq[i]].append(seq[i+1])
# 判断org中是否有seqs中没有的节点
if set(org).difference(nodes):
return False
res = []
queue = deque([start for start in indegree if not indegree[start]])
while queue:
# 要使得有且仅有一个能从 seqs重构出来的序列，则树的每层level节点数必须是1
if len(queue) != 1:
return False
node = queue.popleft()
res.append(node)
# BFS
for neighbor in neighbors[node]:
indegree[neighbor] -= 1
if not indegree[neighbor]:
queue.append(neighbor)
return res == org
网友评论