leetcode拓扑排序专题记录

课程表2问题的两种解法
解法一：拓扑排序，根据节点的入度信息

public class Solution {

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // 先处理极端情况
        if (numCourses <= 0) {
            return new int[0];
        }
        // 邻接表表示
        HashSet<Integer>[] graph = new HashSet[numCourses];
        for (int i = 0; i < numCourses; i++) {
            graph[i] = new HashSet<>();
        }
        // 入度表
        int[] inDegree = new int[numCourses];
        // 遍历 prerequisites 的时候，把 邻接表 和 入度表 都填上
        for (int[] p : prerequisites) {
            graph[p[1]].add(p[0]);
            inDegree[p[0]]++;
        }
        //这里因为List中没有poll方法，所以要用LinkedList声明！
        LinkedList<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.addLast(i);
            }
        }
        ArrayList<Integer> res = new ArrayList<>();
        while (!queue.isEmpty()) {
            // 当前入度为 0 的结点
            Integer inDegreeNode = queue.removeFirst();
            // 加入结果集中
            res.add(inDegreeNode);
            // 下面从图中删去
            // 得到所有的后继课程，接下来把它们的入度全部减去 1
            HashSet<Integer> nextCourses = graph[inDegreeNode];
            for (Integer nextCourse : nextCourses) {
                inDegree[nextCourse]--;
                // 马上检测该结点的入度是否为 0，如果为 0，马上加入队列
                if (inDegree[nextCourse] == 0) {
                    queue.addLast(nextCourse);
                }
            }
        }
        // 如果结果集中的数量不等于结点的数量，就不能完成课程任务，这一点是拓扑排序的结论
        int resLen = res.size();
        if (resLen == numCourses) {
            int[] ret = new int[numCourses];
            for (int i = 0; i < numCourses; i++) {
                ret[i] = res.get(i);
            }
            return ret;
        } else {
            return new int[0];
        }
    }
}

解法二：利用深搜，代码有模板可寻

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        if(numCourses <=0) return new int[0];
        if(prerequisites.length ==0){
            int[] res = new int[numCourses];
            for(int i = 0; i < res.length; i++){
                res[i] = i;
            }
            return res;
        }
        HashSet<Integer>[] graph = new HashSet[numCourses];
        //一旦创建了这样一个数字，就一定要对每个数组元素初始化。
        for(int i = 0; i < numCourses; i++){
            graph[i] = new HashSet<>();
        }
        for(int[] p: prerequisites){
            graph[p[1]].add(p[0]);

        }
        //对每一个元素，创建这样一个
        int[] marked = new int[numCourses];
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < numCourses; i++){
            if(dfs(i,graph,marked,stack)) return new int[0];
        }
        int[] res =  new int[numCourses];
        for(int i = 0; i < numCourses; i++){
            res[i] = stack.pop();
        }
        return res;
    }

    //可以用marked数组，也可以用visited布尔数组记录
    //marked[i] == 2相当于visited[i] == true;
    //marked[i] == 1相当于onstack[i] == true;后者是出现在火星词典的那道题中的解法。
    public boolean dfs(int i, HashSet<Integer>[] graph, int[] marked, Stack<Integer> stack){
        if(marked[i] == 1) return true; // 等于1表示当前正在访问的节点有一次被访问，因此相当于有环；
        if(marked[i] == 2) return false; // 等于2表示当前节点已经被标记为访问过，且不构成环；
        marked[i] =1;
        HashSet<Integer> nextCourses = graph[i];
        for(Integer nextCourse:nextCourses){
            if(dfs(nextCourse, graph,marked,stack)) return true;
        } 
        marked[i] =2;
        stack.push(i);
        return false;
    }
}

火星字典题目解法如下：深搜，其中的dfs是用来判断构造的图中是否有环

class Solution {
    public HashMap<Character,Set<Character>> buildGraph(String[] list){
        HashMap<Character, Set<Character>> graph = new HashMap<>();
        for(int i = 0; i < list.length-1; i++){
            String a = list[i];
            String b = list[i+1];
            for(int j = 0; j < a.length() && j < b.length(); j++){
                //只构建不一样的部分
                if(a.charAt(j) == b.charAt(j)) continue;
                Set<Character> set = graph.getOrDefault(a.charAt(j), new HashSet<Character>());
                set.add(b.charAt(j));
                graph.put(a.charAt(j),set);
                break;
            }
        }
        return graph;
    }
    public String alienOrder(String[] words) {
        HashMap<Character, Set<Character>> graph = buildGraph(words);
        StringBuilder res = new StringBuilder();
        boolean[] visited = new boolean[26];
        for(char c = 'a'; c <='z';c++){
            if(!visited[c-'a'])
                if(graph.containsKey(c) && dfs(c,graph,visited,new boolean[26],res)) return "";
        }
        for(String s:words){
            for(char i: s.toCharArray()){
                if(!visited[i-'a']){
                    res.append(i);
                    visited[i-'a'] = true;
                }

            }
        }
        return res.toString();
    }
    public boolean dfs(char c, HashMap<Character, Set<Character>> graph, boolean[] visited, boolean[] onstack,StringBuilder sb){
        //获取下标
        int index = c - 'a';
        if(onstack[index]) return true;
        if(visited[index]) return false;
        visited[index] = true;
        onstack[index] = true;
        //这个char c 一定是在这个图里面的，以为上面的函数alien中要先判断这个字符在图中containsKey（）
        //重中之重：但是为什么还要再用getOrDefault函数呢，因为上一个函数的HashMap中的value部分Set<Character>部分并没有默认初始化！
        Set<Character> set = graph.getOrDefault(c,new HashSet<Character>());
        for(Character cc: set){
            if(dfs(cc,graph,visited,onstack,sb)) return true;
        }
        onstack[index] = false;
        sb.insert(0,c);
        return false;
    }
}