Graphic leetcode - Sword finger offer II 115. reconstruction sequence (difficulty: medium)

One 、 subject

Given a length of  n  Array of integers for  nums , among  nums  Is in the range of  [1,n]  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  .

about  sequences = [[1,2],[1,3]] , There are two shortest   Supersequence  ,[1,2,3]  and  [1,3,2].

about  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  It's sequential Unique shortest 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 .

Two 、 Example

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 ：

• n == nums.length
• 1 <= n <= 104
• nums yes [1, n] The arrangement of all integers in the range
• 1 <= sequences.length <= 104
• 1 <= sequences[i].length <= 104
• 1 <= sum(sequences[i].length) <= 105
• 1 <= sequences[i][j] <= n
• sequences All arrays of are only Of
• sequences[i] yes nums A subsequence of

3、 ... and 、 Their thinking

According to the meaning , We can put together numbers as Directed graph , According to A topological sort To get the supersequence . For example, let's suppose sequences = [[1,2],[1,3],[2,3]], So the first array [1, 2], We can construct node(1) and node(2) Two nodes , Then from node(1) Point to node(2). such ,node(1) Current “ The degree of ” by 0,node(2) Of “ The degree of ” by 1. Other array elements, and so on . So we can see , The degree of 0 The node of is the head node after the whole sorting , Then enter the degree 1 The node of , Then there is entering degree 2 The node of , And so on . We can according to different degrees , To finally arrange a supersequence . Now let's sequences = [[1,2],[1,3],[2,3]] For example , Look at the specific steps of constructing a unique supersequence , As shown in the figure below ：

Above, we understand the construction process of the unique supersequence , So how to judge whether it is the only supersequence ？ In fact, it is based on To judge . Now let's use sequences = [[1,2],[1,3]] For example . In the first array [1, 2] in ,node(1) The degree of entry is 0,node(2) The degree of entry is 1; In the second array [1, 3] in ,node(1) The penetration is still 0,node(3) The degree of entry is 1. At this time we found that ,node(2) and node(3) The degree of penetration is 0 了 . In fact, we can draw a conclusion ： The first element of the shortest supersequence must be node(1), The second element may be node(2), It could be node(3). Then the uniqueness of the shortest supersequence is not satisfied . Now let's sequences = [[1,2],[1,3]] For example , Look at the specific steps of constructing a non unique supersequence , As shown in the figure below ：

How do we do it in realization . We found that , In the whole process , Determine the penetration value of each node with high frequency , And for each node value Value is 1 <= n <= 104, So we can pass Array structure To store the input value of each node —— Subscript index Represents the node value , Specific value Array[index] Represents the input degree of the node . The details are shown in the following figure ：

Element node element , In fact, we only care about two parts ： node value Value and the set of child nodes it points to , Because it needs to remove weight （ namely ：[1, 2] and [1, 2, 3] in ,1 The node pointed to is 2, instead of 2 and 2）, So we use Set data structure To store the child nodes pointed to . If you find that Set The child node already exists in , Then the input degree of the child node will not change , otherwise , Can perform addition 1 operation . The node element structure is as follows ：

About A topological sort , We can use queue The way to achieve . in other words , When we will sequences After the elements in are transformed into a directed graph , First of all, let's go to 0 Put the elements of into the queue , At this time, judge whether the elements contained in the queue are greater than 1 individual , If it is , Then it means that we will eventually get multiple shortest super sequences , Method returns false. If the number of elements in the queue is 1 individual , Then it conforms to the unique shortest supersequence . Remember after each cycle , Will enter the degree 0 The input degree of the child node of minus one , And will enter 0 Put the element of into the queue . And in each cycle, colleagues will call the queued poll Method enter this value 0 The elements of “ Kicked out ” queue , Prepare for the next round of listing elements . Now let's sequences = [[1,2],[1,3]] For example , Demonstrate how to use queues to achieve topological sorting ：

Four 、 Code implementation

class Solution {
    public boolean sequenceReconstruction(int[] nums, int[][] sequences) {
        int[] inRef = new int[nums.length + 1]; //  Record 【 The degree of 】 frequency 
        Set<Integer>[] ref = new HashSet[nums.length + 1]; //  Used to record each element and its 【 The degree of 】 Mapping of elements 

        /**  step 1： Calculate the of each element 【 The degree of 】 value , And maintain the connection between the two associated nodes  */
        for (int[] sequence : sequences) {
            for (int i = 1; i < sequence.length; i++) { //  First element （index=0） No, 【 The degree of 】, So from index=1 Start loop traversal 
                if (ref[sequence[i - 1]] == null) {
                    ref[sequence[i - 1]] = new HashSet();
                }

                //  return true, Express set There is no such element in , Then you can add 【 Penetration value 】
                if (ref[sequence[i - 1]].add(sequence[i])) {
                    inRef[sequence[i]] += 1; // " The degree of " value +1
                }
            }
        }

        /**  step 2： initialization 【 The degree of 0】 Queues  */
        Queue<Integer> zeroInRefQueue = new ArrayDeque();
        for (int i = 1; i < ref.length; i++) {
            if (inRef[i] == 0) { //  Only will 【 Penetration value 】 by 0 Put in the queue 
                zeroInRefQueue.add(i);
            }
        }
        if (zeroInRefQueue.isEmpty()) { //  There is a cross reference , namely ：A——>B, B——>A
            return false;
        }

        /**  step 3： Follow the node reference path to check whether there are multiple paths  */
        int index = 0;
        while(!zeroInRefQueue.isEmpty()) {
            int i = zeroInRefQueue.peek();
            if (zeroInRefQueue.size() > 1 || nums[index] != i) { //  If 【 Penetration value 】 by 0 The element of is no longer unique , Then the supersequence is not unique 
                return false;
            }
            zeroInRefQueue.poll();
            if (ref[i] != null && !ref[i].isEmpty()) {
                for (Integer num : ref[i]) {
                    inRef[num] -= 1;
                    if (inRef[num] == 0) {
                        zeroInRefQueue.add(num);
                    }
                }
            }
            index++;
        }

        return true;
    }
}

That's all for today's article ：

Writing is not easy to , An article completed by the author in hours or even days , I only want to exchange you for a few seconds give the thumbs-up & Share .

More technical dry goods , Welcome everyone to follow the official account “ Java Muse ”(^o^)/~ 「 Dry cargo sharing , Weekly update 」