😵444 sequence reconstruction

https://leetcode.com/problems/sequence-reconstruction/

答案源自网络，真的是我见过最傻逼的题目，其实意思就是给了一堆array构建一个super sequence，让所有array都是它的subseq，那么就要把array里的元素拿出来重新排列并保证它们在之前每个array里的相对顺序，所以用拓扑排序（保证相对顺序就考虑用拓扑排序）

这道题有个隐含条件是array里没有dup元素，同时给的seq已经是个super seq了所以不用判断

构建map的时候只需要和自己的下一个建立联系，后面顺序自然就成立了

如何判断sup seq有多个：某个时刻queue的size大于1，所谓shortest只是一个烟雾弹，拓扑排序出来的自然就是shortest

public class Solution {
    public boolean sequenceReconstruction(int[] org, int[][] seqs) {
        Map<Integer, Set<Integer>> map = new HashMap<>();
        Map<Integer, Integer> indegree = new HashMap<>();
        
        for(int[] seq: seqs) {
            if(seq.length == 1) {
                if(!map.containsKey(seq[0])) {
                    map.put(seq[0], new HashSet<>());
                    indegree.put(seq[0], 0);
                }
            } else {
                for(int i = 0; i < seq.length - 1; i++) {
                    if(!map.containsKey(seq[i])) {
                        map.put(seq[i], new HashSet<>());
                        indegree.put(seq[i], 0);
                    }

                    if(!map.containsKey(seq[i + 1])) {
                        map.put(seq[i + 1], new HashSet<>());
                        indegree.put(seq[i + 1], 0);
                    }

                    if(map.get(seq[i]).add(seq[i + 1])) {
                        indegree.put(seq[i + 1], indegree.get(seq[i + 1]) + 1);
                    }
                }
            }
        }

        Queue<Integer> queue = new LinkedList<>();
        for(Map.Entry<Integer, Integer> entry: indegree.entrySet()) {
            if(entry.getValue() == 0) queue.offer(entry.getKey());
        }

        int index = 0;
        while(!queue.isEmpty()) {
            int size = queue.size();
            if(size > 1) return false;
            int curr = queue.poll();
            if(index == org.length || curr != org[index++]) return false;
            for(int next: map.get(curr)) {
                indegree.put(next, indegree.get(next) - 1);
                if(indegree.get(next) == 0) queue.offer(next);
            }
        }
        return index == org.length && index == map.size();
    }
}

这是我的版本

拓扑排序要注意indegrees，要防止入度为0的没加上，或者入度重复加了，set的add居然是有返回值的我惊了

class Solution {
    public boolean sequenceReconstruction(int[] nums, List<List<Integer>> sequences) {
        Map<Integer, Set<Integer>> map = new HashMap<>();
        Map<Integer, Integer> indegrees = new HashMap<>();
        
        for (List<Integer> seq : sequences) {
            if (seq.size() == 1) {
                indegrees.put(seq.get(0), indegrees.getOrDefault(seq.get(0), 0));
                continue;
            }
            for (int i = 0; i < seq.size() - 1; i++) {
                Set<Integer> next = map.get(seq.get(i));
                if (next == null) {
                    next = new HashSet<>();
                }
                //这里的if很重要，因为相同的顺序可能出现在多个array里，比如两个array都有5 2
                //这时候要先判断add是不是真的有add，否则入度会重复被加
                if (next.add(seq.get(i + 1))) {
                    map.put(seq.get(i), next);
                    indegrees.put(seq.get(i + 1), indegrees.getOrDefault(seq.get(i + 1), 0) + 1);
                }
                //这一句很重要 不然入度为0的点没法被放进queue里
                indegrees.put(seq.get(i), indegrees.getOrDefault(seq.get(i), 0));
            }
        }
        
        Queue<Integer> queue = new ArrayDeque<>();
        for (Map.Entry<Integer, Integer> entry : indegrees.entrySet()) {
            if (entry.getValue() == 0) {
                queue.offer(entry.getKey());
            }
        }
        int index = 0;
        while (!queue.isEmpty()) {
            if (queue.size() > 1) {
                // System.out.println("return");
                return false;
            }
            int curr = queue.poll();
            // System.out.println(curr);
            index++;
            Set<Integer> next = map.get(curr);
            if (next == null) {
                continue;
            }
            for (int n : next) {
                // System.out.println(n);
                indegrees.put(n, indegrees.get(n) - 1);
                if (indegrees.get(n) == 0) {
                    queue.offer(n);
                }
            }
        }
        System.out.println(index);
        // 这里还是很有必要的，万一nums不是最短呢
        return index == nums.length;
    }
}

一年之后更新，用array代替map，更简单更不容易错

注意那个隐藏条件，subarray中没有重复元素，所以不用考虑一个数有两个set的情况

但是要注意如果set里已经有某个数了indegree就不用再加了

class Solution {
    public boolean sequenceReconstruction(int[] nums, List<List<Integer>> sequences) {
        int n = nums.length;
        int[] indegrees = new int[n + 1];
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (List<Integer> seq : sequences) {
            for (int i = 1; i < seq.size(); i++) {
                Set<Integer> set = map.get(seq.get(i-1));
                if (set == null) {
                    set = new HashSet<>();
                }
                if (set.add(seq.get(i))) {
                    indegrees[seq.get(i)]++;
                }
                map.put(seq.get(i-1), set);
            }
        }
        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 1; i <= n; i++) {
            if (indegrees[i] == 0) {
                queue.offer(i);
            }
        }
        int cnt = 0;
        while (!queue.isEmpty()) {
            if (queue.size() != 1) {
                return false;
            }
            int num = queue.poll();
            if (nums[cnt++] != num) {
                return false;
            }
            Set<Integer> set = map.get(num);
            if (set != null) {
                for (int next : set) {
                    indegrees[next]--;
                    if (indegrees[next] == 0){
                        queue.offer(next);
                    }
                }
            }
        }
        return cnt == nums.length;
    }
}