LintCode 题解丨Facebook面试题：序列重构

判断是否序列 ​org​ 能唯一地由 ​seqs​重构得出. ​org​是一个由从1到n的正整数排列而成的序列，1≤n≤10​^4​​。 重构表示组合成​seqs​的一个最短的父序列 (意思是，一个最短的序列使得所有 ​seqs​里的序列都是它的子序列).

判断是否有且仅有一个能从 ​seqs​重构出来的序列，并且这个序列是​org​。

在线评测地址：LintCode 领扣
​
样例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 也可以，反正只有一个数。

public 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
 */
public boolean sequenceReconstruction(int[] org, int[][] seqs) {
    Map<Integer, Set<Integer>> graph = buildGraph(seqs);
    List<Integer> topoOrder = getTopoOrder(graph);
    
    if (topoOrder == null || topoOrder.size() != org.length) {
        return false;
    }
    for (int i = 0; i < org.length; i++) {
        if (org[i] != topoOrder.get(i)) {
            return false;
        }
    }
    return true;
}

private Map<Integer, Set<Integer>> buildGraph(int[][] seqs) {
    Map<Integer, Set<Integer>> graph = new HashMap();
    for (int[] seq : seqs) {
        for (int i = 0; i < seq.length; i++) {
            if (!graph.containsKey(seq[i])) {
                graph.put(seq[i], new HashSet<Integer>());
            }
        }
    }
    for (int[] seq : seqs) {
        for (int i = 1; i < seq.length; i++) {
            graph.get(seq[i - 1]).add(seq[i]);
        }
    }
    return graph;
}

private Map<Integer, Integer> getIndegrees(Map<Integer, Set<Integer>> graph) {
    Map<Integer, Integer> indegrees = new HashMap();
    for (Integer node : graph.keySet()) {
        indegrees.put(node, 0);
    }
    for (Integer node : graph.keySet()) {
        for (Integer neighbor : graph.get(node)) {
            indegrees.put(neighbor, indegrees.get(neighbor) + 1);
        }
    }
    return indegrees;
}

private List<Integer> getTopoOrder(Map<Integer, Set<Integer>> graph) {
    Map<Integer, Integer> indegrees = getIndegrees(graph);
    Queue<Integer> queue = new LinkedList();
    List<Integer> topoOrder = new ArrayList();
    
    for (Integer node : graph.keySet()) {
        if (indegrees.get(node) == 0) {
            queue.offer(node);
            topoOrder.add(node);
        }
    }
    
    while (!queue.isEmpty()) {
        if (queue.size() > 1) {
            return null;
        }
        
        Integer node = queue.poll();
        for (Integer neighbor : graph.get(node)) {
            indegrees.put(neighbor, indegrees.get(neighbor) - 1);
            if (indegrees.get(neighbor) == 0) {
                queue.offer(neighbor);
                topoOrder.add(neighbor);
            }
        }
    }
    
    if (graph.size() == topoOrder.size()) {
        return topoOrder;
    }
    
    return null;
}

}
更多题解参考：

九章算法 - 帮助更多中国人找到好工作，硅谷顶尖IT企业工程师实时在线授课为你传授面试技巧
​