LintCode VIP 月卡 ¥39.9，→点此处链接选择购买月卡，输入优惠码 7EBE50，即可 39.9 购买，感兴趣的可以用一下~

判断是否序列 org 能唯一地由 seqs 重构得出. org 是一个由从 1 到 n 的正整数排列而成的序列，1≤n≤10^4 。 重构表示组合成 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 也可以，反正只有一个数。

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;     } } 

更多题解参考

LintCode VIP 月卡 ¥39.9，→点此处链接选择购买月卡，输入优惠码 7EBE50，即可 39.9 购买，感兴趣的可以试用一下~

大佬有話說 (0)