关于Leetcode 207 Course Schedule的一点思考...

马上就要硕士毕业了，闲来无事 刷一刷代码，今天做了一个比较有意思的题 LeetCode 207 Course Schedule.

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, is it possible for you to finish all courses?

For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

链接：https://leetcode.com/problems/course-schedule/

一个图的题 拓扑排序嘛~ DFS一下， 看能不能找到环， 或者找到入度为0的点 一个一个删掉。

首先来看DFS：

public boolean canFinish(int numCourses, int[][] prerequisites) {
    ArrayList<Integer>[] map = new ArrayList[numCourses];
    for (int i = 0; i < numCourses; i++) {
        map[i] = new ArrayList<Integer>();
    }
    for (int i = 0; i < prerequisites.length; i++) { // pre -> vertex        

        map[prerequisites[i][1]].add(prerequisites[i][0]);
    }
    int[] visitState = new int[numCourses];
    Arrays.fill(visitState, 0); // 0: unvisited, 1: visiting, 2:visited    

        for (int i = 0; i < numCourses; i++) {
        if (!DFSVisit(i, map, visitState))
            return false;
    }
    return true;
}

private static boolean DFSVisit(int n, ArrayList<Integer>[] map, int[] visitState) {
    if (visitState[n] == 2)
        return true;
    if (visitState[n] == 1)
        return false;
    visitState[n] = 1;
    for (int j = 0; j < map[n].size(); j++) {
        if (!DFSVisit(map[n].get(j), map, visitState))
            return false;
    }
    visitState[n] = 2;
    return true;

}

下面是删除入度为0的点的方式：

public boolean canFinish(int numCourses, int[][] prerequisites) {
    HashMap<Integer,Point> hashMap = new HashMap<>();
    for (int i = 0; i < numCourses ; i++) {
        Point point = new Point(i);
        hashMap.put(i,point);
    }
    for (int[] record:prerequisites)
    {
        hashMap.get(record[0]).getOut().add(record[1]);
        hashMap.get(record[1]).getIn().add(record[0]);
    }
    while (true)
    {
        int pointIdx = findNoInDegree(hashMap);
        if (pointIdx==-1)
        {
            for (Point point:hashMap.values())
            {
                if (point.getIn().size()!=0)
                    return false;
            }
            return true;
        }
        else        {
            Point point = hashMap.get(pointIdx);
            for (int idx: point.getOut())
            {
                hashMap.get(idx).getIn().remove(pointIdx);
            }
            hashMap.remove(pointIdx);
        }
    }
}

public int findNoInDegree(HashMap<Integer,Point> hashMap)
{
    for (Integer key: hashMap.keySet())
    {
        if (hashMap.get(key).getIn().size()==0)
            return key;
    }
    return -1;
}

class Point
{
    int num = 0;
    HashSet<Integer> in;
    HashSet<Integer> out;

    Point(int num)
    {
        this.num = num;
        this.in = new HashSet<>();
        this.out = new HashSet<>();
    }

    public int getNum() {
        return num;
    }

    public void setNum(int num) {
        this.num = num;
    }

    public HashSet<Integer> getOut() {
        return out;
    }

    public void setOut(HashSet<Integer> out) {
        this.out = out;
    }

    public HashSet<Integer> getIn() {
        return in;
    }

    public void setIn(HashSet<Integer> in) {
        this.in = in;
    }
}

比较而言，很明显 第一种方式效率高于第二种，但是第二种方式不免冗杂了些，但是在其他方面，

作为一个程序员的话，哪一种方式好一些呢。

在学校这一年半的学习生涯中，几乎所有的课程（eg：Design Pattern，Software Product Line，

Software Maintenance and Evolutionary）都在强调一点 "Do not think about performance"

那么Performance 到底算是什么呢...
其实就个人理解，performance就是钱，security啦，user friendliness啦，Maintainability啦，就像是商品，用performance去买。
当然花多少，怎么花由产品特性和技术标准决定。