[leetcode/lintcode 題解] 算法面試高頻題：序列重構

描述

判斷是否序列 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           

更多題解參考：

九章官網solution