LeetCode 444. 序列重建

2022-10-07 HGNULB 约 13 分钟

文章信息 6 个分类 4 个标签

分类

题目描述

✅ 444. 序列重建

题意分析

题目目标：给定一个原始序列 org，以及若干条子序列 seqs，判断 org 是否是「唯一」能同时满足所有 seqs 作为其子序列的那个序列。换句话说，要同时验证两件事——org 确实是一个合法解，并且合法解只有它一个。
核心约束：这里的重点不在于「能不能重建」，而在于「重建结果唯一不唯一」。seqs 里的每条子序列只提供了相邻元素之间的先后关系，这是典型的偏序信息；把元素当节点、把「谁必须排在谁前面」当有向边，问题立刻变成图上的拓扑排序。而拓扑序唯一的充要条件是众所周知的：整个排序过程中，任意时刻入度为 0 的节点都恰好只有一个——一旦某一步同时有两个节点可选，就至少存在两个不同的合法拓扑序，唯一性被破坏。第二个信号是 seqs 中的元素可能超出 org 的范围，也可能覆盖不全 org 的所有元素，两种情况都会导致答案为 false，因此必须先做节点集合的规模核对。
边界处理：seqs 可能为空或只含空序列，此时没有任何约束信息，除非 org 也为空否则无法唯一确定；seqs 中可能出现重复的相邻对，重复建边会让入度被多加，必须去重；seqs 中可能出现 org 里没有的数字，或者遗漏了 org 中的某些数字；图中可能存在环，此时拓扑排序无法输出全部节点，同样应判 false；某条 seq 可能只有一个元素，它不产生任何边但确实贡献了一个节点。

解法：拓扑排序判唯一

核心思路

最先想到的可能是逐条验证：对每条 seq 检查它是不是 org 的子序列，全部通过就返回 true。但这只解决了「org 是合法解」这一半，完全没有回答「有没有别的序列也合法」。举例来说，org = [1,2,3] 与 seqs = [[1,2],[1,3]] 时每条都是子序列，可 [1,3,2] 同样满足所有约束，答案应当是 false。瓶颈就在于：验证合法性是局部的，而验证唯一性必须站在全局的约束图上看。
把视角切换到图。seqs 中每一条序列 $[v_1, v_2, \dots, v_k]$ 实际上给出了 k-1 条硬性的先后关系：$v_1$ 必须在 $v_2$ 之前，$v_2$ 必须在 $v_3$ 之前，依此类推。注意不需要给不相邻的元素之间连边，因为先后关系具有传递性，相邻边已经蕴含了全部信息，多连边只会增加代价。这样得到一张有向图，所有满足约束的排列恰好就是这张图的全部拓扑序。于是「唯一重建」等价于「拓扑序存在且唯一，并且那个唯一的拓扑序等于 org」。
唯一性的判定依赖一个经典结论：在基于入度的拓扑排序过程中，若每一步可选的入度为 0 的节点都恰好只有一个，则拓扑序唯一；只要某一步有两个及以上候选，就能通过交换它们的先后顺序构造出另一个合法拓扑序。因此维护的状态是一个候选队列，不变量是：队列中始终存放当前所有前驱已全部就绪、可以立即输出的节点。算法每轮先检查队列规模是否恰好为 1，不为 1 立刻否定；再把唯一的候选取出，与 org 当前位置比对，不一致同样否定；然后把它的所有后继入度减一，减到 0 的入队。整个过程结束后，还要确认输出的节点总数等于 org 的长度——若小于，说明图里有环或有节点始终无法就绪。至于节点集合的核对（seqs 覆盖的元素恰好构成 org 的元素集合），可以在建图前用一次规模比较加上后续逐位比对来共同保证。

正确性分两面：若算法返回真，每一步都只有一个合法候选且恰好等于 org 对应项，最终又输出全部节点，所以 org 是存在且唯一的拓扑序；若 org 能被唯一重建，则任何一步都不可能出现零个、多个候选或与 org 不同的唯一候选，算法也不会误判为假。

解题步骤

第一步：扫一遍 seqs，为每个出现的元素初始化空邻接集合和 0 入度。 indegree 的键集合同时就是节点集合，不需要再维护一份重复的 nodes。邻接表用集合，是为了让重复相邻对只形成一条边。

第二步：比较 indegree 的键数量与 org 长度，不相等直接返回 false。 覆盖少了说明 org 有元素未出现，覆盖多了说明 seqs 含额外元素；两种都不可能唯一重建出 org。

第三步：再扫一遍 seqs，对每条序列的每一对相邻元素 (a, b) 建有向边 a→b，只有当这条边是首次出现时才把 b 的入度加一。 为什么只连相邻对：先后关系可传递，$v_1 \to v_2 \to v_3$ 已经蕴含 $v_1$ 在 $v_3$ 之前，额外连 $v_1 \to v_3$ 不增加任何约束却会把边数从 $O(L)$ 抬到 $O(L^2)$。为什么必须去重后再加入度：重复边会让 b 的入度被多加，导致它的前驱全部处理完后入度仍大于 0，永远无法入队，算法会误判为有环而返回 false。

第四步：把所有入度为 0 的节点放进队列，并准备一个指向 org 的游标 idx。 为什么初始入度为 0 的节点就是起点候选：入度为 0 意味着没有任何元素被要求排在它前面，它可以立即输出。

第五步：循环处理队列，每轮先判断队列规模是否为 1，不是则返回 false。 为什么规模大于 1 就否定：此刻有多个节点都可以合法地放在当前位置，任选其一都能得到一个完整的拓扑序，唯一性被破坏。为什么不需要单独处理规模为 0：循环条件本身就是队列非空，进入循环时规模至少为 1。

第六步：取出唯一候选，与 org[idx] 比对，不同则返回 false，相同则 idx 前进一位。 为什么要逐位比对而不是最后整体比较：提前发现不一致可以立即短路，避免无谓计算；同时这一步也顺带保证了 seqs 涉及的元素值与 org 的元素值完全一致——只要有一个值对不上就会在这里被抓住。为什么要先判 idx >= org.length：防御性写法，避免在异常数据下越界读取。

第七步：把出队节点的所有后继入度减一，减到 0 的入队。 为什么减到 0 才入队：入度代表还有多少个前驱没被输出，归零才说明所有约束都已满足，此时它才真正可选。为什么每条边只触发一次减操作：邻接集合已经去重，遍历一遍就等于恰好处理每条边一次。

第八步：循环结束后返回 idx == org.length。 为什么还要这个收尾判断：如果图中存在环，环上的节点入度永远无法归零，队列会提前变空，此时 idx 小于 org 的长度，应当返回 false。只有把所有节点都成功输出且每一步都唯一、每一步都与 org 吻合，才能确认答案为 true。

以 org = [1,2,3], seqs = [[1,2],[1,3]] 走一遍。 第一遍扫描登记节点 {1,2,3}，规模 3 等于 org 长度 3，通过检查。建边：从 [1,2] 得 1→2，2 的入度变为 1；从 [1,3] 得 1→3，3 的入度变为 1。入度为 0 的只有节点 1，入队。第一轮循环：队列规模为 1，取出 1，与 org[0] = 1 一致，idx 变为 1；处理 1 的后继 2 和 3，两者入度都减为 0，双双入队，此时队列里有两个节点。第二轮循环：队列规模为 2，不等于 1，立即返回 false。这正是期望结果——[1,3,2] 也满足所有子序列约束，重建不唯一。再看一个应当返回 true 的用例 org = [1,2,3], seqs = [[1,2],[1,3],[2,3]]：节点集合仍是 {1,2,3}，规模匹配。建边 1→2、1→3、2→3，入度分别为 1: 0、2: 1、3: 2。初始队列只有 1。第一轮：规模为 1，取出 1 与 org[0] 一致，idx = 1；后继 2 入度减为 0 入队，后继 3 入度减为 1 仍不入队，队列只剩 2。第二轮：规模为 1，取出 2 与 org[1] = 2 一致，idx = 2；后继 3 入度减为 0 入队。第三轮：规模为 1，取出 3 与 org[2] = 3 一致，idx = 3；3 没有后继。队列变空退出，idx 等于 org 长度 3，返回 true。整个过程中每一步都恰好只有一个可选节点，说明拓扑序唯一，且这个唯一序列正是 org。

代码实现

import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

// 核心实现：拓扑排序判唯一，维护必要状态并避免重复处理。
class Solution {
    public boolean sequenceReconstruction(int[] org, List<List<Integer>> seqs) {
        Map<Integer, Set<Integer>> graph = new HashMap<>();
        Map<Integer, Integer> indegree = new HashMap<>();
        for (List<Integer> seq : seqs) {
            for (int v : seq) {
                graph.putIfAbsent(v, new HashSet<>());
                indegree.putIfAbsent(v, 0);
            }
        }
        if (indegree.size() != org.length) {
            return false;
        }

        for (List<Integer> seq : seqs) {
            for (int i = 1; i < seq.size(); i++) {
                int a = seq.get(i - 1);
                int b = seq.get(i);
                if (graph.get(a).add(b)) {
                    indegree.put(b, indegree.get(b) + 1);
                }
            }
        }

        Queue<Integer> queue = new ArrayDeque<>();
        for (int v : indegree.keySet()) {
            if (indegree.get(v) == 0) {
                queue.offer(v);
            }
        }

        int idx = 0;
        while (!queue.isEmpty()) {
            if (queue.size() != 1) {
                return false;
            }
            int cur = queue.poll();
            if (idx >= org.length || cur != org[idx]) {
                return false;
            }
            idx++;

            for (int next : graph.get(cur)) {
                indegree.put(next, indegree.get(next) - 1);
                if (indegree.get(next) == 0) {
                    queue.offer(next);
                }
            }
        }

        return idx == org.length;
    }
}

// 核心实现：拓扑排序判唯一，维护必要状态并避免重复处理。
func sequenceReconstruction(org []int, seqs [][]int) bool {
	graph := make(map[int]map[int]struct{})
	indeg := make(map[int]int)
	for _, seq := range seqs {
		for _, v := range seq {
			if _, ok := graph[v]; !ok {
				graph[v] = make(map[int]struct{})
			}
			if _, ok := indeg[v]; !ok {
				indeg[v] = 0
			}
		}
	}
	if len(indeg) != len(org) {
		return false
	}

	for _, seq := range seqs {
		for i := 1; i < len(seq); i++ {
			a := seq[i-1]
			b := seq[i]
			if _, ok := graph[a][b]; !ok {
				graph[a][b] = struct{}{}
				indeg[b]++
			}
		}
	}

	queue := make([]int, 0)
	for v := range indeg {
		if indeg[v] == 0 {
			queue = append(queue, v)
		}
	}

	idx := 0
	head := 0
	for head < len(queue) {
		if len(queue)-head != 1 {
			return false
		}
		cur := queue[head]
		head++
		if idx >= len(org) || cur != org[idx] {
			return false
		}
		idx++

		for next := range graph[cur] {
			indeg[next]--
			if indeg[next] == 0 {
				queue = append(queue, next)
			}
		}
	}

	return idx == len(org)
}

复杂度分析

时间复杂度：$O(V + E)$，其中 V 是不同元素的个数、E 是去重后的相邻对数量，两者都被 seqs 的总长度界住。凭什么：建图阶段对 seqs 扫描两遍，每个元素和每对相邻元素各被处理常数次；拓扑排序阶段每个节点恰好出队一次、每条边恰好被松弛一次，队列操作和哈希查找均摊都是常数。

空间复杂度：$O(V + E)$。邻接表保存去重后的边，入度表的键同时承担节点集合，队列最多容纳 $V$ 个节点。

关键点总结

「先后关系」类的约束一律翻译成有向边，问题就落进拓扑排序的框架。识别信号是题目给的信息形如「A 必须在 B 之前」，而不管它以序列、字典序还是依赖列表的形式出现。

拓扑序唯一的判据是「每一步入度为 0 的节点恰好一个」，这是本题区别于普通拓扑排序题的核心。理解它的方式是：候选多于一个时，交换任意两个候选的输出顺序都能得到另一个合法序，唯一性立刻被反例推翻。

只连相邻元素的边，靠传递性覆盖其余关系。这不仅是效率优化——把边数从 $O(L^2)$ 降到 $O(L)$——也是正确性的一部分，因为多余的边不会改变拓扑序集合却会显著增加去重负担。

建边必须去重后再累加入度。入度的语义是「还有多少个不同的前驱未就绪」，重复计数会让节点永远无法归零，把一个本该成立的用例误判为有环。

判定题要把所有失败通道列全再动手：节点集合规模不符、某步候选多于一个、某步与 org 不匹配、结束时未输出全部节点。漏掉任何一条都会在特定用例上翻车，这种「穷举失败条件」的习惯在面试中比写对主流程更能体现严谨性。

面试视角：这题是拓扑排序的进阶考法，面试官期待你先说出「约束建图 + 拓扑排序」的框架，再主动补上唯一性判据。常见追问有三个——「为什么不需要连非相邻元素」（传递性）、「重复边为什么必须去重」（入度语义）、「如果只问能否重建而不问唯一怎么办」（去掉队列规模检查即可，退化成标准拓扑排序）。

易错点总结

错误写法：只验证每条 seq 是不是 org 的子序列就返回 true。用例 org = [1,2,3], seqs = [[1,2],[1,3]] → 两条都是子序列于是返回 true，但 [1,3,2] 同样合法，正确答案是 false。

错误写法：建边时不去重，直接对每对相邻元素给入度加一。用例 org = [1,2], seqs = [[1,2],[1,2]] → 节点 2 的入度被加到 2，节点 1 出队后只减到 1，队列提前变空，idx 停在 1，误返回 false，正确答案是 true。

错误写法：不检查队列规模，只做标准拓扑排序再和 org 整体比较。用例 org = [1,2,3], seqs = [[1,2],[1,3]] → 队列中 2 和 3 的出队顺序取决于容器实现，可能恰好得到 [1,2,3] 而返回 true，正确答案是 false。

错误写法：为「保险」把每条 seq 中所有元素两两连边。用例一条长度为 1000 的 seq → 边数从 999 暴涨到约五十万，去重开销和内存双双上升，在多条长序列下直接超时。

错误写法：循环结束后直接返回 true，不检查 idx 是否走完 org。用例 org = [1,2], seqs = [[1,2],[2,1]] → 图中存在环 1→2→1，两个节点入度都为 1，初始队列为空，循环一次都不进就返回 true，正确答案是 false。

错误写法：把入度减到 0 的判断写成小于等于 0。用例存在重复边且未去重的数据 → 同一节点可能被多次入队，队列规模检查失效，还会重复输出同一个元素。

错误写法：假设元素值就是 1 到 n 的连续整数并用数组下标存入度。用例 seqs = [[100, 200]] → 数组越界崩溃，题目并未保证取值范围紧凑，必须用哈希表或先做离散化。

相似题目

题目	难度	考察点
207. 课程表	中等	只判断有无环，不要求输出序列，是拓扑排序的最简形态
210. 课程表 II	中等	需要输出任意一个合法拓扑序，不涉及唯一性判定
269. 火星词典	困难	边要从相邻单词的首个不同字符推导，还要识别前缀矛盾这一非法输入
310. 最小高度树	中等	无向图上的逐层剥叶，展示入度思想在非有向场景下的变体
LCR 115. 序列重建	中等	同题的另一版本，可对照不同数据范围下建图方式的取舍
面试题 04.01. 节点间通路	中等	同为有向图问题但只问可达性，用搜索即可，不需要入度统计