5 March 2020
LeetCode(107) -- 210
by Jerry Zhang
P210. Course Schedule II (Medium)
There are a total of n courses you have to take, labeled from 0 to n-1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.
There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.
My Solution
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
if (numCourses == 0) {
return null;
}
HashSet<Integer> set = new HashSet<>();
for (int i = 0; i < numCourses; i++) {
set.add(i);
}
int[] ans = new int[numCourses];
int[] numOfPre = new int[numCourses];
for (int i = 0; i < prerequisites.length; i++) {
numOfPre[prerequisites[i][0]]++;
}
int numOfEdge = prerequisites.length;
int j = 0;
boolean change = true;
while (change) {
change = false;
for (int i = 0; i < prerequisites.length; i++) {
if (prerequisites[i] != null) {
if (numOfPre[prerequisites[i][1]] == 0) {
if (set.contains(prerequisites[i][1])) {
ans[j] = prerequisites[i][1];
set.remove(prerequisites[i][1]);
j++;
}
numOfPre[prerequisites[i][0]]--;
change = true;
prerequisites[i] = null;
numOfEdge--;
}
}
}
}
if (numOfEdge > 0) {
return new int[0];
}
for (Integer integer : set) {
ans[j] = integer;
j++;
}
return ans;
}
}
42%
Solution
方法一:DFS:
public class P210_CourseScheduleII {
static int WHITE = 1;
static int GRAY = 2;
static int BLACK = 3;
boolean isPossible;
Map<Integer, Integer> color;
Map<Integer, List<Integer>> adjList;
List<Integer> topologicalOrder;
private void init(int numCourses) {
this.isPossible = true;
this.color = new HashMap<>();
this.adjList = new HashMap<>();
this.topologicalOrder = new ArrayList<>();
for (int i = 0; i < numCourses; i++) {
this.color.put(i, WHITE);
}
}
private void dfs(int node) {
if (!this.isPossible) {
return;
}
this.color.put(node, GRAY);
for (Integer neighbor : this.adjList.getOrDefault(node, new ArrayList<>())) {
if (this.color.get(neighbor) == WHITE) {
this.dfs(neighbor);
} else if (this.color.get(neighbor) == GRAY) {
this.isPossible = false;
}
}
this.color.put(node, BLACK);
this.topologicalOrder.add(node);
}
public int[] findOrder(int numCourses, int[][] prerequisites) {
this.init(numCourses);
for (int[] prerequisite : prerequisites) {
int dest = prerequisite[0];
int src = prerequisite[1];
List<Integer> lst = adjList.getOrDefault(src, new ArrayList<>());
lst.add(dest);
adjList.put(src, lst);
}
for (int i = 0; i < numCourses; i++) {
if (this.color.get(i) == WHITE) {
this.dfs(i);
}
}
int[] order;
if (this.isPossible) {
order = new int[numCourses];
for (int i = 0; i < numCourses; i++) {
order[i] = this.topologicalOrder.get(numCourses - i - 1);
}
} else {
order = new int[0];
}
return order;
}
public static void main(String[] args) {
int[][] test = 1;
int[] order = new P210_CourseScheduleII().findOrder(2, test);
System.out.println("order = " + Arrays.toString(order));
}
}
方法二:Using Node Indegree
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
boolean isPossible = true;
Map<Integer, List<Integer>> adjList = new HashMap<Integer, List<Integer>>();
int[] indegree = new int[numCourses];
int[] topologicalOrder = new int[numCourses];
// Create the adjacency list representation of the graph
for (int i = 0; i < prerequisites.length; i++) {
int dest = prerequisites[i][0];
int src = prerequisites[i][1];
List<Integer> lst = adjList.getOrDefault(src, new ArrayList<Integer>());
lst.add(dest);
adjList.put(src, lst);
// Record in-degree of each vertex
indegree[dest] += 1;
}
// Add all vertices with 0 in-degree to the queue
Queue<Integer> q = new LinkedList<Integer>();
for (int i = 0; i < numCourses; i++) {
if (indegree[i] == 0) {
q.add(i);
}
}
int i = 0;
// Process until the Q becomes empty
while (!q.isEmpty()) {
int node = q.remove();
topologicalOrder[i++] = node;
// Reduce the in-degree of each neighbor by 1
if (adjList.containsKey(node)) {
for (Integer neighbor : adjList.get(node)) {
indegree[neighbor]--;
// If in-degree of a neighbor becomes 0, add it to the Q
if (indegree[neighbor] == 0) {
q.add(neighbor);
}
}
}
}
// Check to see if topological sort is possible or not.
if (i == numCourses) {
return topologicalOrder;
}
return new int[0];
}
}
Topological Sorted Order
tags: LeetCode