力扣207. 课程表
力扣207.课程表
原题，题目描述：
题目给出一个整型变量表示要修的课程数量，给出一个二维数组，第二维固定长度只有2，第一维表示后修课程，第二维表示先修课程，必须要先修完先修课程再修后修课程。二维数组的第一维长度不固定。整个二维数组给出了一组课程先后修关系，任务是根据这个二维数组和课程数量判断能不能修完课程。
这应该是一个比较典型的图论的应用，看完题目后的第一想法其实就是感觉就是根据二维数组构建一个图，然后判断这个图有没有环，有环则不行，没环就可以。
我自己思考了一下想出一种深度优先搜索的思路，根据二维数组建一张图，然后从每个节点出发深度优先搜索遍历，判断会不会回到当前节点。根据这个想法我写出了以下代码：
class Solution {
public static class CanFinishNode {
private ArrayList<CanFinishNode> next;
private int val;
public CanFinishNode(int val) {
next = new ArrayList<>();
this.val = val;
}
public void add(CanFinishNode node) {
next.add(node);
}
}
boolean flag = true;
public boolean canFinish(int numCourses, int[][] prerequisites) {
HashMap<Integer, CanFinishNode> map = new HashMap<>();
for (int[] prerequisite : prerequisites) {
CanFinishNode node1;
boolean flag1 = map.containsKey(prerequisite[0]);
if (flag1) {
node1 = map.get(prerequisite[0]);
} else {
node1 = new CanFinishNode(prerequisite[0]);
map.put(prerequisite[0], node1);
}
CanFinishNode node2;
boolean flag2 = map.containsKey(prerequisite[1]);
if (flag2) {
node2 = map.get(prerequisite[1]);
} else {
node2 = new CanFinishNode(prerequisite[1]);
map.put(prerequisite[1], node2);
}
node2.add(node1);
}
map.forEach((integer, node) -> {
canFinishset.add(node);
flag = flag && canFinishDFS(node.next);
canFinishset.remove(node);
});
return flag;
}
Set<CanFinishNode> canFinishset=new HashSet<>();
public boolean canFinishDFS(ArrayList<CanFinishNode> node) {
if (node == null) {
return true;
}
boolean flag = true;
for (CanFinishNode canFinishNode : node) {
if (canFinishset.contains(canFinishNode)) {
return false;
}
canFinishset.add(canFinishNode);
flag = canFinishDFS(canFinishNode.next);
if (!flag) {
return false;
}
canFinishset.remove(canFinishNode);
}
return flag;
}
}
但是这个解法非常耗时，所以没有通过结题，在48/53个用例超时了。仔细分析一下，遍历建图的时候需要耗时，又需要进入递归和哈希运算（包括散列表和set集合），虽然整体分析时间复杂度不算特别高，但是操作数非常多。
我实在是想不出来解法了，于是我看了一样官方解答，官方给出了两种解法，一种基于深度优先，一种基于广度优先。分别从出度和入度出发来做判断，我将两种算法看懂后写出了如下代码：
class Solution {
public static class CanFinishNode {
private ArrayList<Integer> next;
private int val;
public CanFinishNode(int val) {
next = new ArrayList<>();
this.val = val;
}
public void add(int node) {
next.add(node);
}
}
HashMap<Integer, CanFinishNode> map = new HashMap<>();
public boolean canFinish(int numCourses, int[][] prerequisites) {
int[] n = new int[numCourses];
for (int[] i : prerequisites) {
n[i[0]]++;
if (!map.containsKey(i[0])) {
CanFinishNode node = new CanFinishNode(i[0]);
map.put(i[0], node);
}
if (!map.containsKey(i[1])) {
CanFinishNode node = new CanFinishNode(i[1]);
map.put(i[1], node);
node.add(i[0]);
}else {
CanFinishNode node = map.get(i[1]);
node.add(i[0]);
}
}
ArrayDeque<Integer> queue = new ArrayDeque<>();
ArrayList<Integer> visited = new ArrayList<>();
for (int i = 0; i < n.length; i++) {
if (n[i] == 0) {
queue.addLast(i);
}
}
while (!queue.isEmpty()) {
Integer i = queue.removeLast();
visited.add(i);
CanFinishNode node = map.get(i);
if (node!=null){
ArrayList<Integer> next = node.next;
for (Integer integer : next) {
n[integer]--;
if (n[integer] == 0) {
queue.addLast(integer);
}
}
}
}
return visited.size() == numCourses;
}
}
提交后通过，但是打败了百分之16，并不是一个令人满意的结果。仔细看其中有可以优化的地方，首先就是这个类可以去掉，这里类的作用的存储值和next，我们可以直接使用一个二维数组替代掉。同时这里的visited可以直接退化成一个变量。优化后代码如下：
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
int[] n = new int[numCourses];
ArrayList<Integer>[] res=new ArrayList[numCourses];
for (int i = 0; i < numCourses; i++) {
res[i] = new ArrayList<>();
}
for (int[] i : prerequisites) {
n[i[0]]++;
res[i[1]].add(i[0]);
}
ArrayDeque<Integer> queue = new ArrayDeque<>();
for (int i = 0; i < n.length; i++) {
if (n[i] == 0) {
queue.addLast(i);
}
}
int visited=0;
while (!queue.isEmpty()) {
Integer i = queue.removeLast();
visited++;
ArrayList<Integer> next = res[i];
for (Integer integer : next) {
n[integer]--;
if (n[integer] == 0) {
queue.addLast(integer);
}
}
}
return visited == numCourses;
}
}
最后打败百分之80，算得上比较优秀的解法。
力扣207. 课程表
https://www.than.pw/archives/%E5%8A%9B%E6%89%A3207.-%E8%AF%BE%E7%A8%8B%E8%A1%A8