本文主要是介绍Sequence Reconstruction，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Description
中文English
Check whether the original sequence org can be uniquely reconstructed from the sequences in seqs. The org sequence is a permutation of the integers from 1 to n, with 1 ≤ n ≤ 10^4. Reconstruction means building a shortest common supersequence of the sequences in seqs (i.e., a shortest sequence so that all sequences in seqs are subsequences of it). Determine whether there is only one sequence that can be reconstructed from seqs and it is the org sequence.
Have you met this question in a real interview? Yes
Problem Correction
Example
Example 1:
Input:org = [1,2,3], seqs = [[1,2],[1,3]]
Output: false
Explanation:
[1,2,3] is not the only one sequence that can be reconstructed, because [1,3,2] is also a valid sequence that can be reconstructed.
Example 2:
Input: org = [1,2,3], seqs = [[1,2]]
Output: false
Explanation:
The reconstructed sequence can only be [1,2].
Example 3:
Input: org = [1,2,3], seqs = [[1,2],[1,3],[2,3]]
Output: true
Explanation:
The sequences [1,2], [1,3], and [2,3] can uniquely reconstruct the original sequence [1,2,3].
Example 4:
Input:org = [4,1,5,2,6,3], seqs = [[5,2,6,3],[4,1,5,2]]
Output:true思路：就是topological sort，关键是要会建立图和indegreeMap，这题唯一topo解，就是queue size == 1，然后学到的一点技巧就是 用add函数 return true or false 来判断是否indegree +1，否则相同的边，入度会累加两次，是不应该的。最后一个比较trick的地方就是不用收集结果，直接跟结果比较就可以了，就是用org[index++] == node 来比较；
class Solution {public boolean sequenceReconstruction(int[] org, List<List<Integer>> seqs) {if(org == null || seqs == null || seqs.size() == 0) {return false;}HashMap<Integer, HashSet<Integer>> hashmap = new HashMap<Integer, HashSet<Integer>>();HashMap<Integer, Integer> indegree = new HashMap<Integer, Integer>();for(List<Integer> list: seqs) {if(list.size() == 1) {if(!hashmap.containsKey(list.get(0))) {hashmap.put(list.get(0), new HashSet<Integer>());indegree.put(list.get(0), 0);}} else {for(int i = 0; i < list.size() - 1; i++) {int a = list.get(i);int b = list.get(i+1);// a -> b;hashmap.putIfAbsent(a, new HashSet<Integer>());hashmap.putIfAbsent(b, new HashSet<Integer>());indegree.putIfAbsent(a, 0);indegree.putIfAbsent(b, 0);// 用add return false来去重复，因为test case有重复；// 入度不能重复加，如果边相同的话；只能加一次 for same test cases;if(hashmap.get(a).add(b)) {indegree.put(b, indegree.get(b) + 1);}}}}Queue<Integer> queue = new LinkedList<Integer>();for(Integer integer : indegree.keySet()) {if(indegree.get(integer) == 0) {queue.offer(integer);}}int index = 0;while(!queue.isEmpty()) {if(queue.size() > 1) {return false;}Integer node = queue.poll();if(index == org.length || org[index++] != node) {return false;}for(Integer neighbor: hashmap.get(node)) {indegree.put(neighbor, indegree.get(neighbor) - 1);if(indegree.get(neighbor) == 0) {queue.offer(neighbor);}}}return index == org.length && index == hashmap.size();}
}
这篇关于Sequence Reconstruction的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
