[leetcode/lintcode 题解] Amazon面试题

现在你总共有 n 门课需要选，记为 0 到 n - 1.

一些课程在修之前需要先修另外的一些课程，比如要学习课程 0 你需要先学习课程 1 ，表示为[0,1]

• 给定n门课以及他们的先决条件，判断是否可能完成所有课程？

在线评测地址：lintcode领扣

例1:

输入: n = 2, prerequisites = [[1,0]] 
输出: true

例2:

输入: n = 2, prerequisites = [[1,0],[0,1]] 
输出: false

【题解】

对于两门课之间的约束关系，很容易联想到图，我们可以将课抽象为节点，将约束抽象为一条有向边，可以用有向图的相关算法解决问题。拓扑排序正好可以解决这一问题。

算法：拓扑排序

一个合法的选课序列就是一个拓扑序，拓扑序是指一个满足有向图上，不存在一条边出节点在入节点后的线性序列，如果有向图中有环，就不存在拓扑序。可以通过拓扑排序算法来得到拓扑序，以及判断是否存在环。

拓扑排序步骤：

1. 建图并记录所有节点的入度。
2. 将所有入度为0的节点加入队列。
3. 取出队首的元素now，将其加入拓扑序列。
4. 访问所有now的邻接点nxt，将nxt的入度减1，当减到0后，将nxt加入队列。
5. 重复步骤3、4，直到队列为空。
6. 如果拓扑序列个数等于节点数，代表该有向图无环，且存在拓扑序。

复杂度分析

设课程数，即图的节点数为V。

约束数量，即图的边数为E。

时间复杂度O(V + E)

• 建图，扫描一遍所有的边O(E)。
• 每个节点最多入队出队1次，复杂度O(V)。
• 邻接表最终会被遍历1遍，复杂度O(E)。
• 综上，总复杂度为O(E + V)。

空间复杂度O(V + E)

• 邻接表占用O(E + V)的空间。
• 队列最劣情况写占用O(V)的空间。
• 综上，总复杂度为O(V + E)。

public class Solution {
    /*
     * @param numCourses: a total of n courses
     * @param prerequisites: a list of prerequisite pairs
     * @return: true if can finish all courses or false
     */
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List[] graph = new ArrayList[numCourses];
        int[] inDegree = new int[numCourses];

        for (int i = 0; i < numCourses; i++) {
            graph[i] = new ArrayList<Integer>();
        }

        // 建图
        for (int[] edge: prerequisites) {
            graph[edge[1]].add(edge[0]);
            inDegree[edge[0]]++;
        }

        int numChoose = 0;
        Queue queue = new LinkedList();

        // 将入度为 0 的编号加入队列
        for(int i = 0; i < inDegree.length; i++){
            if (inDegree[i] == 0) {
                queue.add(i);
            }
        }

        while (! queue.isEmpty()) {
            int nowPos = (int)queue.poll();
            numChoose++;
            // 将每条边删去，如果入度降为 0，再加入队列
            for (int i = 0; i < graph[nowPos].size(); i++) {
                int nextPos = (int)graph[nowPos].get(i);
                inDegree[nextPos]--;
                if (inDegree[nextPos] == 0) {
                    queue.add(nextPos);
                }
            }
        }

        return numChoose == numCourses;
    }
}

更多题解参见：leetcode/lintcode题解