#Problem

#⭐️⭐️⭐️⭐️⭐️

题目是说有个original sequence是1到n的一个permutation, 比如[1,2,3]或者[2,3,1]. 然后再给一个用二维数组表示的seqs, 比如[[1,2], [1,3]]. 问题是那个original sequence是否是seqs中唯一的shortest super sequence.

1
2
3
4
5
6
7
Input:
org: [1,2,3], seqs: [[1,2],[1,3]]
Output:
false
[1,2,3], [1,3,2]都是valid shortest super sequences
1
2
3
4
5
6
7
Input:
org: [1,2,3], seqs: [[1,2],[1,3],[2,3]]
Output:
false
[1,2,3]是唯一的shortest super sequence

#Solution

题目有点难看懂, 但是理解之后很显然是一个graph和topological sort的题. 因此找shortest super sequence的问题其实就是在找topological sort的结果. 而唯一一个shortest super sequence的意思就是topological sort的结果是否是唯一的.

比如[[1,2],[1,3]]的topological sort就有两种, 1,2,3或者1,3,2.
而[[1,2],[1,3],[2,3]]的topological sort就是唯一的.

#Note

有一些可以剪枝的地方需要留意. 比如seqs里的数字不在[1,n]的范围里.

#Code

#Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
public boolean sequenceReconstruction(int[] org, List<List<Integer>> seqs) {
if (seqs.isEmpty()) return false;
if (org.length == 0) return false;
final int n = org.length;
final Map<Integer, Set<Integer>> graph = new HashMap<>();
final int[] indegree = new int[n + 1];
for (final List<Integer> seq : seqs) {
for (int i = 0; i < seq.size() - 1; i++) {
final int src = seq.get(i);
final int dst = seq.get(i + 1);
if (src <= 0 || src > n || dst <= 0 || dst > n || src == dst) return false;
graph.putIfAbsent(src, new HashSet<>());
graph.putIfAbsent(dst, new HashSet<>());
if (!graph.get(src).contains(dst)) {
graph.get(src).add(dst);
indegree[dst]++;
}
}
if (!seq.isEmpty()) {
graph.putIfAbsent(seq.get(seq.size() - 1), new HashSet<>());
}
}
if (graph.size() != org.length) return false;
final Queue<Integer> queue = new LinkedList<>();
for (int i = 1; i <= n; i++) {
if (indegree[i] == 0) queue.offer(i);
if (queue.size() > 1) return false;
}
final int[] visited = new int[org.length + 1];
while (!queue.isEmpty()) {
final int front = queue.poll();
visited[front] = 1;
for (final int adj : graph.get(front)) {
indegree[adj]--;
if (indegree[adj] == 0) {
queue.offer(adj);
if (queue.size() > 1) return false;
}
}
}
for (int i = 1; i <= n; i++) {
if (visited[i] == 0) return false;
}
return true;
}
}

Comments