九章算法 | 爱彼迎面试题:序列重构
程序员文章站
2022-03-07 22:34:07
...
描述
判断是否序列 org 能唯一地由 seqs重构得出. org是一个由从1到n的正整数排列而成的序列,1≤n≤104。 重构表示组合成seqs的一个最短的父序列 (意思是,一个最短的序列使得所有 seqs里的序列都是它的子序列).
判断是否有且仅有一个能从 seqs重构出来的序列,并且这个序列是org。
样例1
输入:org = [1,2,3], seqs = [[1,2],[1,3]]
输出: false
解释:
[1,2,3] 并不是唯一可以被重构出的序列,还可以重构出 [1,3,2]
样例2
输入: org = [1,2,3], seqs = [[1,2]]
输出: false
解释:
能重构出的序列只有 [1,2].
样例3
输入: org = [1,2,3], seqs = [[1,2],[1,3],[2,3]]
输出: true
解释:
序列 [1,2], [1,3], 和 [2,3] 可以唯一重构出 [1,2,3].
样例4
输入:org = [4,1,5,2,6,3], seqs = [[5,2,6,3],[4,1,5,2]]
输出:true
题解
九章算法班里讲过的拓扑排序,只要保证 queue 里最多同时只有一个元素即可。 所以这是 queue 用 list 然后每次 pop 也可以,反正只有一个数。
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):
graph = self.build_graph(seqs)
topo_order = self.topological_sort(graph)
return topo_order == org
def build_graph(self, seqs):
# initialize graph
graph = {}
for seq in seqs:
for node in seq:
if node not in graph:
graph[node] = set()
for seq in seqs:
for i in range(1, len(seq)):
graph[seq[i - 1]].add(seq[i])
return graph
def get_indegrees(self, graph):
indegrees = {
node: 0
for node in graph
}
for node in graph:
for neighbor in graph[node]:
indegrees[neighbor] += 1
return indegrees
def topological_sort(self, graph):
indegrees = self.get_indegrees(graph)
queue = []
for node in graph:
if indegrees[node] == 0:
queue.append(node)
topo_order = []
while queue:
if len(queue) > 1:
# there must exist more than one topo orders
return None
node = queue.pop()
topo_order.append(node)
for neighbor in graph[node]:
indegrees[neighbor] -= 1
if indegrees[neighbor] == 0:
queue.append(neighbor)
if len(topo_order) == len(graph):
return topo_order
return None
上一篇: java模板引擎freemarker
下一篇: Freemarker模板引擎