[亚马逊面试OA2] Order Dependency 排课

2016-12-05  本文已影响0人  酸辣粉_2329

图论里面的基础问题。
有一堆课程，每个课程都有先后，比如：要上B，就必须先学完A，要上C，又必须先学完B。

例子.png
图中的例子：
0是1,3,4的先驱，4是1,5的先驱，1和3是2的先驱
这样的话，一个学生要上完所有的课，可能的顺序就是：[0,4,1,3,5,2]。这只是一种可能，只要能够上完，就算是正确。
给定了两个类： 
    public class Course {
        String course = "";
        public Course(String str) {
            course = str;
        }
    }

    public class Dependency {
        Course cur;
        Course pre;
        public Dependency(Course cur, Course pre) {
            this.cur = cur;
            this.pre = pre;
        }
    }

输入是Dependency的数组，输出要求是Course的数组。
函数的signature长这样： public List<Course> find(List<Dependency> list)

这种题，不会做真就不会做。要是我不知道什么叫拓扑排序（Topological Sort），根本就是递归懵逼。
这道题就是典型的拓扑排序。
拓扑排序就是拿来干这种事的，只要有先后顺序的，想想它准没错。

停！STOP！

怎么就直接说拓扑排序了呢？大家都没有发现，万一这个图中有环该怎么办？
在leetcode里面也有，就合着一块写了，不想看的就往下拉，题目的分析在下面~

问题就来了，如何检测有向图中是否有环。
BFS？DFS？反正图，总跑不了这两个。想想我们人是怎么看有没有环的，不就是沿着每条路看有没有回头的？DFS就是它了！
这个算法叫什么着色来着，算法导论里面也写得很详细易懂。

有环.png
上面图就有环

这里用的算法叫做三色法。
当遍历到某一个节点时，节点可能会出现三种状态，这三种可能的状态用颜色来标记，便于理解。
首先定义一下三色（也就是三个状态）：

  1. 白色：代表此节点从来没有被访问过
  2. 灰色：代表此节点在当前DFS遍历中被访问过
  3. 黑色：代表此节点在之前的DFS遍历中被访问过 且 从此节点出发的DFS也走完了的
算法的基本思想就是：

先在图中选出白色的节点，DFS遍历：

举个例子

上图为例。

  1. 先选择2节点开始DFS，标记2为灰色。
  2. 走到4，发现4是白色（没有被访问过），标记为灰色
    2.1： 发现4没有邻居了，返回后把4标记为黑色
  3. 回到2，再访问3，标记3为灰色
    3.1 ：3节点可以继续往下走，走到1，发现1也是白色，标记为灰色
    3.2 ：从1节点往下走，发现2是1的邻居，但是2是灰色的，说明有环，返回！

如果图里没有环，最终所有的节点都会被标记成黑色。（当然，island这种东西不考虑）

上代码

LeetCode: [207. Course Schedule]

public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        if (numCourses <= 1 || prerequisites == null || prerequisites.length == 0) {
            return true;
        }
        ArrayList<Integer>[] graph = new ArrayList[numCourses];
        // 把int[][]转换成adjacency list
        // 在graph中，index是每一个课程
        // 所连接的arraylist是这个课程所相连的其他所有课程
        for (int i = 0; i < prerequisites.length; i++) {
            if (graph[prerequisites[i][0]] == null) {
                graph[prerequisites[i][0]] = new ArrayList<>();
            }
            graph[prerequisites[i][0]].add(prerequisites[i][1]);
        }
        // mark每个cell中具有3个值，0,1,2
        // 0 代表 没有被访问过
        // 1 代表 正在被访问
        int[] mark = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            if (!dfs(mark, graph, i)) {
                return false;
            }
        }

        return true;
    }
    
    private boolean dfs(int[] mark, ArrayList[] graph, int course) {
        if (mark[course] == 1) {
            return false;
        } else if (mark[course] == 2) {
            return true;
        } else {
            mark[course] = 1; // 现在正在访问中
        }

        // 继续访问该课程相连的所有课程
        if (graph[course] != null) {
            for (int i = 0; i < graph[course].size(); i++) {
                if (!dfs(mark, graph, (int)graph[course].get(i))) {
                    return false;
                }
            }
        }
        mark[course] = 2;
        return true;
    }
}

这方法是比较经典，也比较快的方法，leetcode里面击败了来自全球的96%的Java代码

好，下面进入正题

拓扑排序

数据结构：
  1. 图的表示：Adjacency List
  1. 一个入度记录表：HashMap
  2. BFS必备数据结构：Queue
算法思路：

入度代表的是这个节点被指向的次数。在例子那张图中，1节点的入度为2， 0节点的入度为0，以此类推。
找入度为0的节点，BFS找它的所有邻居，然后把找到的所有邻居在入度记录表里面的入度数减一，如果某个邻居节点的入度数变成了0，那么加入Queue里面，成为下一个BFS的起点。

其实说白了，就是先挑没有prerequisite的课上，上完之后看有没有解锁的课，如果有，那么接着上，如果没有，看看有没有其他的课没有prerequisite。就像游戏里面什么修仙练级之类的……

上代码
public class OrderDependency {
    public static class Order {
        String order = "";
        public Order(String str) {
            order = str;
        }
    }

    public static class Dependency {
        Order cur;
        Order pre;
        public Dependency(Order cur, Order pre) {
            this.cur = cur;
            this.pre = pre;
        }
    }

    public static List<Order> find(List<Dependency> list) {
        List<Order> result = new ArrayList<>();
        if (list == null || list.size() == 0) {
            return result;
        }
        int totalOrder = 0;
        Map<Order, List<Order>> adjList = new HashMap<>();
        Map<Order, Integer> indegree = new HashMap<>();
        Queue<Order> queue = new LinkedList<>();

        // fill indegree and adjList
        for (Dependency dep : list) {
            Order cur = dep.cur;
            Order pre = dep.pre;
            // add to adjList
            if (adjList.containsKey(pre)) {
                adjList.get(pre).add(cur);
            } else {
                adjList.put(pre, new ArrayList<>());
                adjList.get(pre).add(cur);
            }
            // add to indegree
            if (indegree.containsKey(cur)) {
                indegree.put(cur, indegree.get(cur) + 1);
            } else {
                indegree.put(cur, 1);
            }
            if (!indegree.containsKey(pre)) {
                indegree.put(pre, 0);
            }
        }

        for (Order o : indegree.keySet()) {
            if (indegree.get(o) == 0) {
                queue.offer(o);
            }
        }

        // BFS
        while (!queue.isEmpty()) {
            Order order = queue.poll();
            indegree.remove(order);
            result.add(order);
            if (adjList.containsKey(order)) {
                for (Order cur : adjList.get(order)) {
                    if (indegree.containsKey(cur)) {
                        indegree.put(cur, indegree.get(cur) - 1);
                    }
                    if (indegree.get(cur) == 0) {
                        queue.offer(cur);
                    }
                }
            }
        }

        if (indegree.size() != 0) {
            return null;
        }
        return result;
    }
}
上一篇下一篇

猜你喜欢

热点阅读