Jianzhi offer II 115. reconstruction sequence: topological sorting construction problem

Title Description

This is a LeetCode Upper The finger of the sword Offer II 115. Reconstruction sequence , The difficulty is secondary .

Tag : 「 graph theory 」、「 A topological sort 」、「 Drawing 」、「 graph theory BFS」

Given a length of n Array of integers for nums , among nums Is in the range of The arrangement of integers . One is also provided 2D An array of integers  sequences, among  sequences[i]  yes  nums  The subsequence .

Check nums Is it the only shortest   Supersequence . The shortest Supersequence yes The shortest length Sequence , And all sequences  sequences[i]  Are its subsequences . For a given array  sequences, There may be multiple valid Supersequence .

• for example , about   sequences = [[1,2],[1,3]] , There are two shortest Supersequence , [1,2,3] and [1,3,2] .
• And for   sequences = [[1,2],[1,3],[1,2,3]], The only possible shortest Supersequence yes [1,2,3] . [1,2,3,4] Is a possible supersequence , But not the shortest .

If nums Is the only shortest sequence Supersequence , Then return to true , Otherwise return to false .

Subsequence One can delete some elements from another sequence or not delete any elements , A sequence that does not change the order of the remaining elements .

Example 1：

 Input ：nums = [1,2,3], sequences = [[1,2],[1,3]]

 Output ：false

 explain ： There are two possible supersequences ：[1,2,3] and [1,3,2].
 Sequence  [1,2]  yes [1,2,3] and [1,3,2] The subsequence .
 Sequence  [1,3]  yes [1,2,3] and [1,3,2] The subsequence .
 because  nums  Is not the only shortest supersequence , So back false.

Example 2：

 Input ：nums = [1,2,3], sequences = [[1,2]]

 Output ：false

 explain ： The shortest possible supersequence is  [1,2].
 Sequence  [1,2]  Is its subsequence ：[1,2].
 because  nums  Not the shortest supersequence , So back false.

Example 3：

 Input ：nums = [1,2,3], sequences = [[1,2],[1,3],[2,3]]

 Output ：true

 explain ： The shortest possible supersequence is [1,2,3].
 Sequence  [1,2]  It's a subsequence of it ：[1,2,3].
 Sequence  [1,3]  It's a subsequence of it ：[1,2,3].
 Sequence  [2,3]  It's a subsequence of it ：[1,2,3].
 because  nums  Is the only shortest supersequence , So back true.

Tips ：

• nums  yes     The arrangement of all integers in the range
• sequences  All arrays of are only Of
• sequences[i]  yes   nums A subsequence of

A topological sort + structure

For convenience , We make sequences by ss.

According to the meaning , If we can make use of all Construct a unique sequence , And the sequence is similar to nums identical , Then return to True, Otherwise return to False.

Each one See as right The context constraints of the included points , We can transform the problem into a topological ordering problem .

Use all Construct a new map ： about , We convert it into points -> -> ... -> The directed graph of , At the same time, count the penetration of each point .

Then run the topological sorting on the new graph , Construct the corresponding topological sequence , And nums Contrast .

Implementation , Because in the process of topology sorting , The order of the points is the topological order , Therefore, we do not need to completely save the entire topological order , Just use one variable loc To record the subscript of the current topological order , There will be some And Just make a comparison .

In the process of topological order, if there is It's not equal to （ The constructed scheme is similar to nums Different ） Or it is found that there are more than queue elements in a certain expansion process individual （ At this time, the possible reasons are :「 The initial penetration is There is more than one point or there are some points that are not at all in 」 or 「 The newly generated penetration of a single expansion is There is more than one point , That is, the topological order is not unique 」）, Then return directly False,

Java Code ：

class Solution {
    int N = 10010, M = N, idx;
    int[] he = new int[N], e = new int[M], ne = new int[M], in = new int[N];
    void add(int a, int b) {
        e[idx] = b;
        ne[idx] = he[a];
        he[a] = idx++;
        in[b]++;
    }
    public boolean sequenceReconstruction(int[] nums, int[][] ss) {
        int n = nums.length;
        Arrays.fill(he, -1);
        for (int[] s : ss) {
            for (int i = 1; i < s.length; i++) add(s[i - 1], s[i]);
        }
        Deque<Integer> d = new ArrayDeque<>();
        for (int i = 1; i <= n; i++) {
            if (in[i] == 0) d.addLast(i);
        }
        int loc = 0;
        while (!d.isEmpty()) {
            if (d.size() != 1) return false;
            int t = d.pollFirst();
            if (nums[loc++] != t) return false;
            for (int i = he[t]; i != -1; i = ne[i]) {
                int j = e[i];
                if (--in[j] == 0) d.addLast(j);
            }
        }
        return true;
    }
}

TypeScript Code ：

const N = 10010, M = N
const he: number[] = new Array<number>(N).fill(-1), e = new Array<number>(N).fill(0), ne = new Array<number>(N).fill(0), ind = new Array<number>(N).fill(0);
let idx = 0
function add(a: number, b: number): void {
    e[idx] = b
    ne[idx] = he[a]
    he[a] = idx++
    ind[b]++
}
function sequenceReconstruction(nums: number[], ss: number[][]): boolean {
    he.fill(-1); ind.fill(0)
    idx = 0
    const n = nums.length
    for (const s of ss) {
        for (let i = 1; i < s.length; i++) add(s[i - 1], s[i])
    }
    const stk: number[] = new Array<number>()
    let head = 0, tail = 0
    for (let i = 1; i <= n; i++) {
        if (ind[i] == 0) stk[tail++] = i
    }
    let loc = 0
    while (head < tail) {
        if (tail - head > 1) return false
        const t = stk[head++]
        if (nums[loc++] != t) return false
        for (let i = he[t]; i != -1; i = ne[i]) {
            const j = e[i]
            if (--ind[j] == 0) stk[tail++] = j
        }
    }
    return true
};

• Time complexity ： The complexity of drawing construction is ; The complexity of running topological sorting is . The overall complexity is
• Spatial complexity ：

Last

This is us. 「 Brush through LeetCode」 The first of the series The finger of the sword Offer II 115 piece , The series begins with 2021/01/01, As of the start date LeetCode I have in common 1916 questions , Part of it is a locked question , We will finish all the questions without lock first .

In this series , In addition to explaining the idea of solving problems , And give the most concise code possible . If the general solution is involved, there will be corresponding code templates .

In order to facilitate the students to debug and submit code on the computer , I've built a warehouse ：https://github.com/SharingSource/LogicStack-LeetCode .

In the warehouse address , You can see the links to the series 、 The corresponding code of the series 、LeetCode Links to the original problem and other preferred solutions .

More, more, more popular 「 written examination / interview 」 Relevant information can be found in the beautifully arranged Gather new bases