LeetCode 444. Sequence Reconstruction (Java版; Medium)

男娘i 2023-07-04 06:09 34阅读 0赞

### [welcome to my blog][] ###

## LeetCode 444. Sequence Reconstruction (Java版; Medium) ##

#### 题目描述 ####

Check whether the original sequence org can be uniquely reconstructed from the sequences in seqs. The org sequence is a permutation of the integers from 1 to n, with 1 ≤ n ≤ 104. Reconstruction means building a shortest common supersequence of the sequences in seqs (i.e., a shortest sequence so that all sequences in seqs are subsequences of it). Determine whether there is only one sequence that can be reconstructed from seqs and it is the org sequence.
    
    Example 1:
    
    Input:
    org: [1,2,3], seqs: [[1,2],[1,3]]
    
    Output:
    false
    
    Explanation:
    [1,2,3] is not the only one sequence that can be reconstructed, because [1,3,2] is also a valid sequence that can be reconstructed.
    Example 2:
    
    Input:
    org: [1,2,3], seqs: [[1,2]]
    
    Output:
    false
    
    Explanation:
    The reconstructed sequence can only be [1,2].
    Example 3:
    
    Input:
    org: [1,2,3], seqs: [[1,2],[1,3],[2,3]]
    
    Output:
    true
    
    Explanation:
    The sequences [1,2], [1,3], and [2,3] can uniquely reconstruct the original sequence [1,2,3].
    Example 4:
    
    Input:
    org: [4,1,5,2,6,3], seqs: [[5,2,6,3],[4,1,5,2]]
    
    Output:
    true

#### 第一次做; 拓扑排序; 核心:拓扑排序流程, 1)邻接矩阵adj 2)入度表 3)入度为零的队列; 细节: 哈希表中如果value是list, 那么一定要用map.put, 吃了两次亏了 ####

/* permutation是排列的意思 拓扑排序是否只有一种结果 拓扑排序流程: 1. */
    class Solution { 
        public boolean sequenceReconstruction(int[] org, List<List<Integer>> seqs) { 
            //input check
            //
            int n = org.length;
            //检查seqs中是否有n个不同的数字
            HashSet<Integer> set = new HashSet<>();
            for(List<Integer> list : seqs){ 
                for(Integer i : list){ 
                    set.add(i);
                }
            }
            if(set.size()!=n)
                return false;
            //创建邻接矩阵; 使用哈希表
            HashMap<Integer, List<Integer>> map = new HashMap<>();
            for(List<Integer> list : seqs){ 
                for(int i=0; i<list.size()-1; i++){ 
                    List<Integer> al = map.getOrDefault(list.get(i), new ArrayList<Integer>());
                    al.add(list.get(i+1));
                    //又忘记写put了, 第二次... 如果哈希表的value是list, 一定要写map.put
                    map.put(list.get(i), al);
                }
            }
            //创建入度表; 数字取值范围1~n, 所以数组长为n+1, 只用其中的1~n
            int[] degree = new int[n+1];
            for(Integer key : map.keySet()){ 
                for(Integer i : map.get(key)){ 
                    degree[i]++;
                }
            }
            //检查是否只有一个入度为0的数字; 如果有多个入度为零的数字, 最终的结果不唯一, 返回false
            int zeroInDegreeCount = 0;
            int index = 0;
            for(int i=1; i<=n; i++)
                if(degree[i]==0){ 
                    zeroInDegreeCount++;
                    index = i;
                }
    
            if(zeroInDegreeCount!=1)
                return false;
            //创建队列, 存放入度为零的节点
            Queue<Integer> queue = new LinkedList<>();
            queue.add(index);
            //循环
            index=0;
            while(!queue.isEmpty()){ 
                int cur = queue.poll();
                //cur应该与org对应
                if(cur!=org[index])
                    return false;
                index++;
                //与cur相邻的数字的入度减一
                if(map.containsKey(cur)){ 
                    for(Integer a : map.get(cur)){ 
                        degree[a]--;
                        if(degree[a]==0){ 
                            queue.add(a);
                            //入度为0的节点大于一个, 结果不唯一, 返回false
                            if(queue.size()>1)
                                return false;
                        }
                    }
                }
            }
            //索引越界表示org和拓扑排序一样, 返回true
            return index==n;
        }
    }

#### [力扣优秀题解][Link 1] ####

public boolean sequenceReconstruction(int[] org, List<List<Integer>> seqs) { 
            int n = org.length;
    
            if (n == 0 || seqs.size() == 0) { 
                return false;
            }
    
            // 考虑seqs里头元素为空列表的情况, 已经数字超过n或者<=0的情况
            Set<Integer> numSet = new HashSet<>();
            for (List<Integer> list : seqs) { 
                for (Integer num: list) { 
                    if (num <= 0 || num > n) { 
                        return false;
                    }
                    numSet.add(num);
                }
            }
    
            if (numSet.size() < n) { 
                return false;
            }
    
            ArrayList<Integer>[] adj = new ArrayList[n + 1];
    
            for (int i = 1; i <= n; i++) { 
                adj[i] = new ArrayList<>();
            }
    
            // 构建邻接表
            for (int i = 0; i < seqs.size(); i++) { 
                List<Integer> pair = seqs.get(i);
                for (int j = 0; j < pair.size() - 1; j++) { 
                    adj[pair.get(j)].add(pair.get(j+1));
                }
            }
    
            // 计算每个节点的入度
            int[] inDegree = new int[n + 1];
    
            for (int i = 1; i <= n; i++) { 
                for (int j = 0; j < adj[i].size(); j++) { 
                    int w = adj[i].get(j);
                    inDegree[w]++;
                }
            }
    
            // 计算入度为0的节点，添加到队列中
            LinkedList<Integer> queue = new LinkedList<>();
            for (int i = 1; i <= n; i++) { 
                if (inDegree[i] == 0) { 
                    queue.addLast(i);
                }
            }
    
            // 入度为0的节点有多个，就会产生多种序列，或者没有入度为0的，不满足题目要求
            if (queue.size() != 1) { 
                return false;
            }
    
            int index = 0;
            while (!queue.isEmpty()) { 
                int num = queue.removeFirst();
                if (org[index] != num) { 
                    return false;
                }
                index++;
    
                // 删除当前节点后，所有当前节点的下一个节点的入度为0的个数，超过1则说明序列不唯一
                int nextZeroInDegreeCount = 0;
                for (int j = 0; j < adj[num].size(); j++) { 
                    int w = adj[num].get(j);
                    inDegree[w]--;
                    if (inDegree[w] == 0) { 
                        nextZeroInDegreeCount++;
                        if (nextZeroInDegreeCount > 1) { 
                            return false;
                        }
    
                        queue.addLast(w);
                    }
                }
            }
    
            return index == n;
        }

[welcome to my blog]: https://littlehaes.com
[Link 1]: https://leetcode-cn.com/problems/sequence-reconstruction/solution/java-tuo-bu-pai-xu-by-purerain/