描述

判斷是否序列 org 能唯一地由 seqs 重構(gòu)得出. org 是一個(gè)由從1 到 n 的正整數(shù)排列而成的序列进鸠，1 ≤ n ≤ 10^4揪垄。 重構(gòu)表示組合成 seqs 的一個(gè)最短的父序列 (意思是幽崩，一個(gè)最短的序列使得所有 seqs 里的序列都是它的子序列).
判斷是否有且僅有一個(gè)能從 seqs 重構(gòu)出來的序列逊谋，并且這個(gè)序列是org取刃。

樣例

給定 org = [1,2,3], seqs = [[1,2],[1,3]]
返回 false
解釋:
[1,2,3] 并不是唯一可以被重構(gòu)出的序列吧彪，還可以重構(gòu)出 [1,3,2]
給出 org = [1,2,3], seqs = [[1,2]]
返回 false
解釋:
能重構(gòu)出的序列只有 [1,2].
給定 org = [1,2,3], seqs = [[1,2],[1,3],[2,3]]
返回 true
解釋:
序列 [1,2], [1,3], 和 [2,3] 可以唯一重構(gòu)出 [1,2,3].
給定org = [4,1,5,2,6,3], seqs = [[5,2,6,3],[4,1,5,2]]
返回 true

思路

用 seqs 進(jìn)行拓?fù)渑判虻玫綌?shù)組待侵，判斷 org 是否是唯一解

代碼

public class Solution {
    /**
     * @param org a permutation of the integers from 1 to n
     * @param seqs a list of sequences
     * @return true if it can be reconstructed only one or false
     */
    public boolean sequenceReconstruction(int[] org, int[][] seqs) {
        Map<Integer, Set<Integer>> map = new HashMap<Integer, Set<Integer>>();
        Map<Integer, Integer> indegree = new HashMap<Integer, Integer>();
        
        // 給 org 中每個(gè)元素進(jìn)行 map 和度的初始化
        for (int num : org) {
            map.put(num, new HashSet<Integer>());
            indegree.put(num, 0);
        }

        int n = org.length;
        int count = 0;
        // seq 是 seqs 的一維數(shù)組
        for (int[] seq : seqs) {
            count += seq.length;
            // seq[0] 和 seq[1] ... seq[n] 要分開寫，因?yàn)?i - 1 在 i = 0 時(shí)會(huì)越界
            if (seq.length >= 1 && (seq[0] <= 0 || seq[0] > n)) {
                return false;
            }

            // seq 有兩個(gè)以上元素時(shí)
            for (int i = 1; i < seq.length; i++) {
                // seq 中元素不符合 org 中要求
                if (seq[i] <= 0 || seq[i] > n) {
                    return false;
                }
                // 檢查 seq[i] 和 seq[i - 1] 間有沒有映射姨裸，沒有建立個(gè)映射
                // 實(shí)際上就是去重復(fù)秧倾，然后添加 hash 并且統(tǒng)計(jì)度
                if (map.get(seq[i - 1]).add(seq[i])) {
                    indegree.put(seq[i], indegree.get(seq[i]) + 1);
                }
            }
        }

        // 所有 seq 的長度加一起應(yīng)該大于等于 n，seq 中可能存在重復(fù)元素
        if (count < n) {
            return false;
        }
        
        // bfs  
        // 度為 0 的加入隊(duì)列
        Queue<Integer> q = new ArrayDeque<Integer>();
        for (int key : indegree.keySet()) {
            if (indegree.get(key) == 0) {
                q.add(key);
            }
        }
        
    // 用 seqs 進(jìn)行拓?fù)渑判虻玫叫碌慕M合序列啦扬，和org每個(gè)位置一一對(duì)比
        int cnt = 0;
        
        
        // 因?yàn)槭俏ㄒ粯?gòu)成中狂，所以每個(gè)元素的先序應(yīng)該只有一個(gè)，即度為1
        // 只有每次queue中只有一個(gè)元素的時(shí)候扑毡，產(chǎn)生的序列才是唯一的
        while (q.size() == 1) {
            int ele = q.poll();
            for (int next : map.get(ele)) {
                indegree.put(next, indegree.get(next) - 1);
                if (indegree.get(next) == 0) {
                    q.add(next);
                }
            }
            // 判斷新的序列每個(gè)位置和 org 相不相等
            if (ele != org[cnt]) {
                return false;
            }
            cnt++;
        }
        
    // 判斷新構(gòu)造的數(shù)組元素總數(shù)和 org 相不相等
        // 可能會(huì)出現(xiàn)新構(gòu)造的數(shù)組是 org 的子集或者 org 是新構(gòu)造的數(shù)組的子集
        return cnt == org.length;
    }
}