LeetCode——剑指 Offer II 115. 重建序列

大佬，牛！！！

• 题目：给你一个二维数组sequences，然后里面每一行都是nums的子序列。然后问一下这个些子序列能不能确定唯一的最短父序列。然后这个序列是nums。然后就是这里面的数是1到n全部数组的组合，也就是不会重复。
• 我的思路：其实这个题，跟nums的关系不大，我也想到了用拓扑排序，但是不知道怎么写。
• 大佬的思路：要求，任何时候，入度为0的节点的个数只能是1。换句话说，我们构造的这个东西，他是一个线性的。然后就是如何构造这个东西，然后再检验这个东西是不是线性的，如果是的话，那么他一定是nums了。这里还有一个疑惑，就是如果这个数，在sequences中压根没出现呢？其实这个时候就是初始化的入度数组的时候，初始化就是0的，然后如果存在这种情况，那么入度为0的个数一定是大于1的。直接就return false了。那么问题就是如何构建我说的这个东西了，其实就是map和set，其中map的key表示出发点，set表示能到的点也就是map的value。然后遍历sequences构建这个map即可
• 技巧：拓扑排序

java代码

class Solution {
    public boolean sequenceReconstruction(int[] nums, int[][] sequences) {
        // 入度为0的点只有一个，则一定是一个最短的超序列
        int n = nums.length;
        Map<Integer, Set<Integer>> edge = new HashMap<>();
        int[] inDegree = new int[n + 1];
        for (int[] sequence : sequences) {
            for (int i = 1; i < sequence.length; i++) {
                int from = sequence[i - 1];// 起始
                int to = sequence[i];// 终止
                // 包含这条边
                if (edge.containsKey(from) && edge.get(from).contains(to)) {
                    continue;
                }
                // 加入这条边
                edge.putIfAbsent(from, new HashSet<>());
                edge.get(from).add(to);
                inDegree[to]++;// 入度加1
            }
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i < inDegree.length; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);// 入度是0的节点
            }
        }
        while (!queue.isEmpty()) {
            // 入度大于1，则一定是不唯一的，因为可以有多条路可以选
            if (queue.size() > 1) {
                return false;
            }


            Integer from = queue.poll();// 取出队头元素
            Set<Integer> toSet = edge.get(from);
            if (toSet == null) {
                continue;
            }
            for (int to : toSet) {
                inDegree[to]--;// 你的入队有我form提供的，所以--
                if (inDegree[to] == 0) {// 如果是等于0，那么就加入到队列。说明你是新的开始。
                    queue.offer(to);
                }
            }
        }
        return true;
    }
}

• 总结：拓扑排序的题目还是没有怎么做过的，包括图的入度和出度等，这次也是给自己提个醒。附上大佬链接。