题目描述
给定一个长度为 n 的整数数组 nums ，其中 nums 是范围为 [1，n] 的整数的排列。还提供了一个 2D 整数数组 sequences ，其中 sequences[i] 是 nums 的子序列。
检查 nums 是否是唯一的最短 超序列 。最短 超序列 是 长度最短 的序列，并且所有序列 sequences[i] 都是它的子序列。对于给定的数组 sequences ，可能存在多个有效的 超序列 。
- 例如，对于
sequences = [[1,2],[1,3]] ，有两个最短的 超序列 ，[1,2,3] 和 [1,3,2] 。
- 而对于
sequences = [[1,2],[1,3],[1,2,3]] ，唯一可能的最短 超序列 是 [1,2,3] 。[1,2,3,4] 是可能的超序列，但不是最短的。
如果 nums 是序列的唯一最短 超序列 ，则返回 true ，否则返回 false 。
子序列 是一个可以通过从另一个序列中删除一些元素或不删除任何元素，而不改变其余元素的顺序的序列。
示例 1：
输入：nums = [1,2,3], sequences = [[1,2],[1,3]]
输出：false
解释：有两种可能的超序列：[1,2,3]和[1,3,2]。
序列 [1,2] 是[1,2,3]和[1,3,2]的子序列。
序列 [1,3] 是[1,2,3]和[1,3,2]的子序列。
因为 nums 不是唯一最短的超序列，所以返回false。
示例 2：
输入：nums = [1,2,3], sequences = [[1,2]]
输出：false
解释：最短可能的超序列为 [1,2]。
序列 [1,2] 是它的子序列：[1,2]。
因为 nums 不是最短的超序列，所以返回false。
示例 3：
输入：nums = [1,2,3], sequences = [[1,2],[1,3],[2,3]]
输出：true
解释：最短可能的超序列为[1,2,3]。
序列 [1,2] 是它的一个子序列：[1,2,3]。
序列 [1,3] 是它的一个子序列：[1,2,3]。
序列 [2,3] 是它的一个子序列：[1,2,3]。
因为 nums 是唯一最短的超序列，所以返回true。
提示：
n == nums.length1 <= n <= 104nums 是 [1, n] 范围内所有整数的排列1 <= sequences.length <= 1041 <= sequences[i].length <= 1041 <= sum(sequences[i].length) <= 1051 <= sequences[i][j] <= nsequences 的所有数组都是 唯一 的sequences[i] 是 nums 的一个子序列
注意：本题与主站 444 题相同：https://leetcode.cn/problems/sequence-reconstruction/
解法
方法一：拓扑排序
我们可以先遍历每个子序列 seq，对于每个相邻的元素 $a$ 和 $b$，我们在 $a$ 和 $b$ 之间建立一条有向边 $a \to b$。同时统计每个节点的入度，最后将所有入度为 $0$ 的节点加入队列中。
当队列中的节点个数等于 $1$ 时，我们取出队首节点 $i$，将 $i$ 从图中删除，并将 $i$ 的所有相邻节点的入度减 $1$。如果减 $1$ 后相邻节点的入度为 $0$，则将这些节点加入队列中。重复上述操作，直到队列的长度不为 $1$。此时判断队列是否为空，如果不为空，说明有多个最短超序列，返回 false；如果为空，说明只有一个最短超序列，返回 true。
时间复杂度 $O(n + m)$，空间复杂度 $O(n + m)$。其中 $n$ 和 $m$ 分别是节点的个数和边的个数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | class Solution:
def sequenceReconstruction(
self, nums: List[int], sequences: List[List[int]]
) -> bool:
n = len(nums)
g = [[] for _ in range(n)]
indeg = [0] * n
for seq in sequences:
for a, b in pairwise(seq):
a, b = a - 1, b - 1
g[a].append(b)
indeg[b] += 1
q = deque(i for i, x in enumerate(indeg) if x == 0)
while len(q) == 1:
i = q.popleft()
for j in g[i]:
indeg[j] -= 1
if indeg[j] == 0:
q.append(j)
return len(q) == 0
|
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 | class Solution {
public boolean sequenceReconstruction(int[] nums, List<List<Integer>> sequences) {
int n = nums.length;
int[] indeg = new int[n];
List<Integer>[] g = new List[n];
Arrays.setAll(g, k -> new ArrayList<>());
for (var seq : sequences) {
for (int i = 1; i < seq.size(); ++i) {
int a = seq.get(i - 1) - 1, b = seq.get(i) - 1;
g[a].add(b);
++indeg[b];
}
}
Deque<Integer> q = new ArrayDeque<>();
for (int i = 0; i < n; ++i) {
if (indeg[i] == 0) {
q.offer(i);
}
}
while (q.size() == 1) {
int i = q.poll();
for (int j : g[i]) {
if (--indeg[j] == 0) {
q.offer(j);
}
}
}
return q.isEmpty();
}
}
|
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 | class Solution {
public:
bool sequenceReconstruction(vector<int>& nums, vector<vector<int>>& sequences) {
int n = nums.size();
vector<int> indeg(n);
vector<int> g[n];
for (auto& seq : sequences) {
for (int i = 1; i < seq.size(); ++i) {
int a = seq[i - 1] - 1, b = seq[i] - 1;
g[a].push_back(b);
++indeg[b];
}
}
queue<int> q;
for (int i = 0; i < n; ++i) {
if (indeg[i] == 0) {
q.push(i);
}
}
while (q.size() == 1) {
int i = q.front();
q.pop();
for (int j : g[i]) {
if (--indeg[j] == 0) {
q.push(j);
}
}
}
return q.empty();
}
};
|
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 | func sequenceReconstruction(nums []int, sequences [][]int) bool {
n := len(nums)
indeg := make([]int, n)
g := make([][]int, n)
for _, seq := range sequences {
for i, b := range seq[1:] {
a := seq[i] - 1
b -= 1
g[a] = append(g[a], b)
indeg[b]++
}
}
q := []int{}
for i, x := range indeg {
if x == 0 {
q = append(q, i)
}
}
for len(q) == 1 {
i := q[0]
q = q[1:]
for _, j := range g[i] {
indeg[j]--
if indeg[j] == 0 {
q = append(q, j)
}
}
}
return len(q) == 0
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | function sequenceReconstruction(nums: number[], sequences: number[][]): boolean {
const n = nums.length;
const g: number[][] = Array.from({ length: n }, () => []);
const indeg: number[] = Array(n).fill(0);
for (const seq of sequences) {
for (let i = 1; i < seq.length; ++i) {
const [a, b] = [seq[i - 1] - 1, seq[i] - 1];
g[a].push(b);
++indeg[b];
}
}
const q: number[] = indeg.map((v, i) => (v === 0 ? i : -1)).filter(v => v !== -1);
while (q.length === 1) {
const i = q.pop()!;
for (const j of g[i]) {
if (--indeg[j] === 0) {
q.push(j);
}
}
}
return q.length === 0;
}
|
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 | class Solution {
func sequenceReconstruction(_ nums: [Int], _ sequences: [[Int]]) -> Bool {
let n = nums.count
var indegree = [Int](repeating: 0, count: n)
var graph = Array(repeating: [Int](), count: n)
for sequence in sequences {
for i in 1..<sequence.count {
let a = sequence[i - 1] - 1
let b = sequence[i] - 1
graph[a].append(b)
indegree[b] += 1
}
}
var queue = [Int]()
for i in 0..<n {
if indegree[i] == 0 {
queue.append(i)
}
}
while queue.count == 1 {
let i = queue.removeFirst()
for neighbor in graph[i] {
indegree[neighbor] -= 1
if indegree[neighbor] == 0 {
queue.append(neighbor)
}
}
}
return queue.isEmpty
}
}
|