LeetCode LCR 115. 序列重建

2026-03-28 HGNULB 约 7 分钟

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

分类

LeetCode 中等 119 经典题变种挑战剑指 Offer 剑指 Offer（专项突击版）

题目描述

✅ LCR 115. 序列重建

题意分析

nums 是 1 到 n 的排列，sequences 的每一行给出一部分元素的先后关系。判断这些子序列是否唯一确定 nums 作为最短公共超序列：既要能够重建目标，也不能存在另一种同样短的合法顺序。代码中的 org、seqs 分别对应这两个参数。

解法：唯一拓扑序校验

核心思路

[!blue]

每行序列中，相邻元素 a、b 表示 a 必须在 b 前面，建立有向边 a -> b 即可。更远元素间的关系由这些边传递得到，不必再为所有元素对加边。满足全部约束的排列正是这张图的拓扑序。

先登记输入中出现过的全部元素，并检查节点数量是否等于目标长度。缺少的目标元素不必出现在这些子序列的最短公共超序列中，不能认定整个目标已被重建；当全部 n 个不同元素都被覆盖时，公共超序列至少长为 n，合法的拓扑排列恰好长为 n，所以已经最短。

普通拓扑排序只需任选零入度节点，本题还要求每一步只有一个候选。若同时有两个零入度节点，它们之间没有尚待满足的先后约束，可以选择不同的先输出者，无法唯一确定下一项；若每步只有一个且最终能输出全部节点，每一项都被强制确定，拓扑序就是唯一的。

取出唯一候选后，再与 org[idx] 比较，保证重建出的顺序确实是目标顺序，而不只是某个唯一顺序。然后将后继的剩余入度减一，归零时入队。Go 用数组加 head 作为队列，有效候选数是 len(queue)-head，已取出的前缀不能计入。

当前邻接结构是集合，同一条边只保存一次，入度也只对新边增加一次。最后仍需检查输出长度；队列提前耗尽而节点尚未输出完，说明约束图有环，不能成功重建。

解题步骤

登记所有出现过的元素，初始化邻接集合和入度；节点数与目标长度不符时返回 false。

为每行的相邻元素建立有向边，仅对新边增加目标节点入度。

将全部零入度节点入队，令目标下标 idx = 0。

每轮若有效队列长度不为 1，返回 false；否则取出唯一候选，与目标当前位置比较。

匹配后推进 idx，减少所有后继入度，将新归零节点入队。

队列耗尽时，只有输出数量等于目标长度才返回 true。

代码实现

// 队列中每一轮必须只有一个候选，并且要与 org 的当前位置一致。
class Solution {
    public boolean sequenceReconstruction(int[] org, int[][] seqs) {
        Map<Integer, Set<Integer>> graph = new HashMap<>();
        Map<Integer, Integer> indegree = new HashMap<>();
        Set<Integer> nodes = new HashSet<>();

        for (int[] seq : seqs) {
            for (int v : seq) {
                nodes.add(v);
                graph.putIfAbsent(v, new HashSet<>());
                indegree.putIfAbsent(v, 0);
            }
        }

        if (nodes.size() != org.length) {
            return false;
        }

        for (int[] seq : seqs) {
            for (int i = 1; i < seq.length; i++) {
                int a = seq[i - 1];
                int b = seq[i];

                if (graph.get(a).add(b)) {
                    indegree.put(b, indegree.get(b) + 1);
                }
            }
        }

        Queue<Integer> queue = new ArrayDeque<>();

        for (int v : nodes) {
            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;
    }
}

// 队列中每一轮必须只有一个候选，并且要与 org 的当前位置一致。
func sequenceReconstruction(org []int, seqs [][]int) bool {
    graph := make(map[int]map[int]struct{})
    indeg := make(map[int]int)
    nodes := make(map[int]struct{})

    for _, seq := range seqs {
        for _, v := range seq {
            nodes[v] = struct{}{}
            if _, ok := graph[v]; !ok {
                graph[v] = make(map[int]struct{})
            }
            if _, ok := indeg[v]; !ok {
                indeg[v] = 0
            }
        }
    }
    if len(nodes) != 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 nodes {
        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(L+V+E)$，L 为所有输入序列的总长度，V 为不同元素数，E 为去重后的边数。读入全部序列后，每个节点和每条边只处理一次。

空间复杂度：$O(V+E)$，保存节点、邻接集合、入度和队列。

关键点总结

[!green]

覆盖全部元素保证目标没有多余项，并使长度为 n 的合法排列成为最短公共超序列。

每轮只有一个零入度候选保证唯一性，逐项与目标比较保证重建对象正确。

相邻关系通过传递性覆盖整行顺序，重复边的存储与入度计数必须一致。

最终完整输出才能确认成功，不能把队列耗尽直接当作已经重建。

易错点总结

[!yellow]

Java 的 sequences 参数是 int[][]；nums 是 1 到 n 的排列，题目并非没有值域约束。

每一步必须只有一个入度 0 候选，且与目标当前位置一致，才能证明拓扑序唯一。

所有目标元素都要由输入序列覆盖；重复边的去重与入度计算保持一致，最终输出数量也要完整。

相似题目

题目	难度	关联与区别
210. 课程表 II	中等	原题只要任意拓扑序，本题还要求顺序唯一并与指定序列一致。
269. 火星词典	困难	同样从多个局部顺序构建偏序图，本题进一步检查每一步是否只有一个可选节点。

.article-image.is-loading { width: var(--article-image-width, 100%); height: auto; } .article-image.is-loading img { position: static; width: auto !important; height: auto !important; opacity: 1; pointer-events: auto; } .article-image-spinner { display: none; }

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/73516289

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！