LeetCode LCR 115. 序列重建

Categories:

题目描述
思路分析
1. 解法一：拓扑排序 + 唯一性校验（推荐）
相似题目

题目描述

✅ LCR 115. 序列重建

思路分析

解法一：拓扑排序 + 唯一性校验（推荐）

核心思路：

建图并统计入度，同时保证所有数字都出现过。

使用队列进行拓扑排序，每一轮队列大小必须为 1 才能保证唯一序列。

出队顺序需要与 org 完全一致，否则无法唯一重建。

复杂度分析：

时间复杂度：O(total)，其中 total 表示所有序列元素总数。

空间复杂度：O(n + m)，其中 n 为节点数，m 为边数。

import java.util.*;

class Solution {
    public boolean sequenceReconstruction(int[] org, List<List<Integer>> seqs) {
        int n = org.length;
        Map<Integer, Set<Integer>> graph = new HashMap<>();
        int[] indeg = new int[n + 1];
        boolean[] seen = new boolean[n + 1];

        for (int i = 1; i <= n; i++) {
            graph.put(i, new HashSet<>());
        }

        for (List<Integer> seq : seqs) {
            for (int v : seq) {
                if (v < 1 || v > n) {
                    return false;
                }
                seen[v] = true;
            }
            for (int i = 0; i + 1 < seq.size(); i++) {
                int u = seq.get(i);
                int v = seq.get(i + 1);
                if (graph.get(u).add(v)) {
                    indeg[v]++;
                }
            }
        }

        for (int i = 1; i <= n; i++) {
            if (!seen[i]) {
                return false;
            }
        }

        Deque<Integer> queue = new ArrayDeque<>();
        for (int i = 1; i <= n; i++) {
            if (indeg[i] == 0) {
                queue.offer(i);
            }
        }

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

            for (int next : graph.get(cur)) {
                indeg[next]--;
                if (indeg[next] == 0) {
                    queue.offer(next);
                }
            }
        }

        return idx == n;
    }
}

func sequenceReconstruction(org []int, seqs [][]int) bool {
    n := len(org)
    graph := make([]map[int]struct{}, n+1)
    indeg := make([]int, n+1)
    seen := make([]bool, n+1)

    for i := 1; i <= n; i++ {
        graph[i] = make(map[int]struct{})
    }

    for _, seq := range seqs {
        for _, v := range seq {
            if v < 1 || v > n {
                return false
            }
            seen[v] = true
        }
        for i := 0; i+1 < len(seq); i++ {
            u, v := seq[i], seq[i+1]
            if _, ok := graph[u][v]; !ok {
                graph[u][v] = struct{}{}
                indeg[v]++
            }
        }
    }

    for i := 1; i <= n; i++ {
        if !seen[i] {
            return false
        }
    }

    queue := []int{}
    for i := 1; i <= n; i++ {
        if indeg[i] == 0 {
            queue = append(queue, i)
        }
    }

    idx := 0
    for len(queue) > 0 {
        if len(queue) != 1 {
            return false
        }
        cur := queue[0]
        queue = queue[1:]

        if org[idx] != cur {
            return false
        }
        idx++

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

    return idx == n
}

相似题目

题目	难度	考察点
207. 课程表	中等	拓扑排序
210. 课程表 II	中等	拓扑排序
1136. 并行课程	中等	拓扑排序
802. 找到最终的安全状态	中等	有向图
269. 火星词典	困难	拓扑排序

本文作者: HGNULB

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