LC207 Course Schedule

Problem

There are a total of numCourses courses you have to take, labeled from 0 to numCourses-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?

Example 1:

1
2
3
4
Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take. 
             To take course 1 you should have finished course 0. So it is possible.

Example 2:

1
2
3
4
5
Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: 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.

Constraints:

  • The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
  • You may assume that there are no duplicate edges in the input prerequisites.
  • 1 <= numCourses <= 10^5
Think

拓扑排序

  1. vector存放所有的edges，inDegree & outNodes；

  2. 建立一个queue存放所有的入度=0的节点；

  3. 当该队列不为空的时候，取出一个节点，cnt++，将这个节点的所有outNode的inDegree-1，如果这之后outNode的inDegree=0，则加入队列；

  4. 判断cnt是否等于节点的数目。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Node{
public:
    int val;
    int inDegree;
    vector<Node*> outNodes;
    Node(int value){
        val = value;
        inDegree = 0;
        outNodes = vector<Node*>();
    }
};
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    vector<Node*> nodes(numCourses);
    for(int i = 0; i < numCourses; i++){
        nodes[i] = new Node(i);
    }
    for(auto edge: prerequisites){
        nodes[edge[1]]->outNodes.push_back(nodes[edge[0]]);
        nodes[edge[0]]->inDegree++;
    }
    queue<Node*> q;
    for(auto n: nodes){
        if(n->inDegree == 0) q.push(n);
    }
    int cnt = 0;
    while(!q.empty()){
        Node* cur = q.front();
        q.pop();
        cnt++;
        for(auto next: cur->outNodes){
            next->inDegree--;
            if(next->inDegree == 0){
                q.push(next);
            }
        }
    }
    return cnt == numCourses;
}

LC210 Course Schedule II

Problem

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.

Example 1:

1
2
3
4
Input: 2, [[1,0]] 
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished   
             course 0. So the correct course order is [0,1] .

Example 2:

1
2
3
4
5
Input: 4, [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3] or [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both     
             courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. 
             So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3] .

Note:

  1. The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
  2. You may assume that there are no duplicate edges in the input prerequisites.
Think

在上一题的基础上，计算cnt++的时候将pop出的点放到结果数组里即可。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Node{
public:
    int val;
    int inDegree;
    vector<Node*> outNodes;
    Node(int value){
        val = value;
        inDegree = 0;
        outNodes = vector<Node*>();
    }
};
class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int> res(numCourses, -1);
        vector<Node*> nodes(numCourses);
        for(int i = 0; i < numCourses; i++){
            nodes[i] = new Node(i);
        }
        for(auto edge: prerequisites){
            nodes[edge[1]]->outNodes.push_back(nodes[edge[0]]);
            nodes[edge[0]]->inDegree++;
        }
        queue<Node*> q;
        for(auto n: nodes){
            if(n->inDegree == 0) q.push(n);
        }
        int cnt = 0;
        while(!q.empty()){
            Node* cur = q.front();
            q.pop();
            res[cnt++] = cur->val;
            for(auto next: cur->outNodes){
                next->inDegree--;
                if(next->inDegree == 0){
                    q.push(next);
                }
            }
        }
        if(cnt == numCourses) return res;
        else return {};
    }
};

LC329 Longest Increasing Path in a Matrix

Problem

Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example 1:

1
2
3
4
5
6
7
8
Input: nums = 
[
  [9,9,4],
  [6,6,8],
  [2,1,1]
] 
Output: 4 
Explanation: The longest increasing path is [1, 2, 6, 9].

Example 2:

1
2
3
4
5
6
7
8
Input: nums = 
[
  [3,4,5],
  [3,2,6],
  [2,2,1]
] 
Output: 4 
Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.
Think

拓扑结构为，每一个节点只能向上下左右四个节点的位置进行遍历，因此只需要判断当前节点的上下左右四个节点满足：

  1. 比当前节点的值小
  2. outDegree=0

相当于从叶节点开始向根节点遍历，所以在求解outDegree数组的时候，需要计算的是周围所有满足值比当前节点大的节点（相当于是求解下一层的节点）。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
int longestIncreasingPath(vector<vector<int>>& matrix) {
    if(matrix.empty() || matrix[0].empty()) return 0;
    vector<int> dx = {0, 1, 0, -1}, dy = {1, 0, -1, 0};
    int m = matrix.size(), n = matrix[0].size();
    vector<vector<int>> dp(m + 2, vector<int>(n + 2, 0));
    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= n; j++){
            dp[i][j] = matrix[i - 1][j - 1];
        }
    }
    vector<vector<int>> outDegree(m + 2, vector<int>(n + 2, 0));
    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= n; j++){
            for(int k = 0; k < 4; k++){
                if(dp[i][j] < dp[i + dx[k]][j + dy[k]]){
                    outDegree[i][j]++;
                }
            }
        }
    }
    vector<vector<int>> q;
    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= n; j++){
            if(outDegree[i][j] == 0){
                q.push_back({i, j});
            }
        }
    }
    int res = 0;
    while(!q.empty()){
        res++;
        vector<vector<int>> newQ;
        for(auto cur: q){
            for(int i = 0; i < 4; i++){
                if(dp[cur[0]][cur[1]] > dp[cur[0] + dx[i]][cur[1] + dy[i]]){
                    if(--outDegree[cur[0] + dx[i]][cur[1] + dy[i]] == 0){
                        newQ.push_back({cur[0] + dx[i], cur[1] + dy[i]});
                    }
                }
            }
        }
        q = newQ;
    }
    return res;
}

Review

拓扑排序是一类比较特殊的遍历问题，其特殊性在于如何确定下一个要遍历的节点的方式。一般的BFS或者DFS是通过加入子节点的方式，而拓扑排序则是通过加入当前入度为0的点来实现的，也就是说对于一个拓扑排序的场景来说，我们必须要找到一个有序性，即有向无环图(DAG)，从而确定每一个点的入度。