LC444. Sequence Reconstruction
给定int[ ] org和int[[ ]] seqs，求根据seqs的顺序能否唯一构成org。典型的拓扑排序问题，建立邻接表和入度表，利用队列进行排序，唯一的含义就是每次更新队列只有一个元素的入度为0并且所有的元素都进行过排序的过程。一开始的错误在于以为seqs中列出了所有的1V先后顺序蠢哭…
Code
public class Solution {
// typical topological sort problem
// unique -> for each number in org, only one indegree == 0
public boolean sequenceReconstruction(int[] org, int[][] seqs) {
// if(seqs.length == 0) return false;
HashMap<Integer, HashSet<Integer>> map = new HashMap<>();
HashMap<Integer, Integer> indegree = new HashMap<>();
for(int[] seq: seqs){
if(seq.length == 1){
if(!map.containsKey(seq[0])) {
map.put(seq[0], new HashSet<>());
indegree.put(seq[0], 0);
}
}else{
for(int i = 0; i < seq.length-1; i++){
if(seq[i] <= 0 || seq[i] > org.length) return false;
if(!map.containsKey(seq[i])){
map.put(seq[i], new HashSet<>());
indegree.put(seq[i], 0);
}
if(!map.containsKey(seq[i + 1])) {
map.put(seq[i + 1], new HashSet<>());
indegree.put(seq[i + 1], 0);
}
if(map.get(seq[i]).add(seq[i + 1])) {
indegree.put(seq[i + 1], indegree.get(seq[i + 1]) + 1);
}
} // for i
} // else
} // for seq
Queue<Integer> queue = new LinkedList<Integer>();
for(int key: indegree.keySet()){
if(indegree.get(key) == 0) queue.offer(key);
}
int count = 0;
while(!queue.isEmpty()){
if(queue.size() > 1) return false;
int cur = queue.poll();
for(int nex: map.get(cur)){
indegree.put(nex, indegree.get(nex)-1);
if(indegree.get(nex) == 0) queue.offer(nex);
}
count++;
}
return count == org.length && map.size() == org.length;
}
}
seqs中可能有各种奇怪的东西混进去，注意边界条件。
O(n*k)， n = seqs.length, k = average length of each seq