207/210-课程表

LeetCode

发布日期: 2022-03-03

LeetCode 207. Course Schedule

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
Return true if you can finish all courses. Otherwise, return false.

Example 1:

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: true

method：拓扑排序

广度优先搜索

邻接表存图，并记录每个节点的入度，把入度为0的节点入队，每次取出一个节点，把它的后置节点的入度减1，入度变为0同样入队，如果是有向无环图，每个节点都会入队一次，否则有些节点没能入队，以此作为判断依据

bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    int cnt = 0;
    vector<int> indegree(numCourses, 0);
    vector<vector<int>> edge(numCourses, vector<int>());
    for (auto& p : prerequisites) {
        // p[1] -> p[0]
        indegree[p[0]]++;   // 后继节点的入度增加
        edge[p[1]].push_back(p[0]);
    }
    queue<int> q;
    for (int i = 0; i < numCourses; i++) {
        if (indegree[i] == 0) q.push(i);
    }
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        cnt++;
        for (auto& e : edge[x]) {
            indegree[e]--;
            if (indegree[e] == 0) q.push(e);
        }
    }
    return cnt == numCourses;
}

LeetCode 210. Course Schedule II

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

Example 1:

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

method

需要记录节点出队的顺序

vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
    map<int, vector<int>> adjacent;
    vector<int> indegree(numCourses, 0);
    for (auto courses : prerequisites) {
        adjacent[courses[1]].push_back(courses[0]);
        indegree[courses[0]]++;
    }
    queue<int> q;
    for (int i = 0; i < numCourses; i++) {
        if (!indegree[i]) q.push(i);
    }
    vector<int> res;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        res.push_back(cur); // 记录出队顺序
        for (auto course : adjacent[cur]) {
            indegree[course]--;
            if (!indegree[course]) q.push(course);
        }
    }
    if (res.size() != numCourses) {
        return {};
    }
    return res;
}

LeetCode 630. 课程表 III

这里有 n 门不同的在线课程，按从 1 到 n 编号。给你一个数组 courses ，其中 courses[i] = [durationi, lastDayi] 表示第 i 门课将会持续上 durationi 天课，并且必须在不晚于 lastDayi 的时候完成。

你的学期从第 1 天开始。且不能同时修读两门及两门以上的课程。

返回你最多可以修读的课程数目。

示例 1：

输入：courses = [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
输出：3
解释：
这里一共有 4 门课程，但是你最多可以修 3 门：
首先，修第 1 门课，耗费 100 天，在第 100 天完成，在第 101 天开始下门课。
第二，修第 3 门课，耗费 1000 天，在第 1100 天完成，在第 1101 天开始下门课程。
第三，修第 2 门课，耗时 200 天，在第 1300 天完成。
第 4 门课现在不能修，因为将会在第 3300 天完成它，这已经超出了关闭日期。

method: 贪心

先按截至时间从小到大排序，先选截止时间小的，这样后面能选的机会就越大
如果当前这门课不能选，就看之前选过的有没有比这门课学习时间长的，有的话就替换它

用优先队列存储之前学过的课程的学习时间，从大到小排序，这样就能知道当前无法学习的这门课是否可以替换掉已学课程里学习时间最长的

int scheduleCourse(vector<vector<int>>& courses) {
    sort(courses.begin(), courses.end(), [](const auto& a, const auto& b) {
        return a[1] < b[1];
    });
    priority_queue<int> q;  // 记录学过的课程，按学习时间从大到小排序
    int sum = 0;
    for (auto c : courses) {
        if (sum + c[0] <= c[1]) {   // 表示这门课可以学
            sum += c[0];
            q.push(c[0]);
        }
        else if (!q.empty() && c[0] < q.top()) {    // 看能不能替换
            sum -= q.top();
            sum += c[0];
            q.pop();
            q.push(c[0]);
        }
    }
    return q.size();
}

LeetCode 1462. 课程表 IV

你总共需要上 numCourses 门课，课程编号依次为 0 到 numCourses-1 。你会得到一个数组 prerequisite ，其中 prerequisites[i] = [ai, bi] 表示如果你想选 bi 课程，你必须先选 ai 课程。

你也得到一个数组 queries ，其中 queries[j] = [uj, vj]。对于第 j 个查询，您应该回答课程 uj 是否是课程 vj 的先决条件。

返回一个布尔数组 answer ，其中 answer[j] 是第 j 个查询的答案。

method 1: DFS

直接DFS会超时，注意这里也不用回溯

graph存储(i,j)关系，true表示i是j的前继节点，这样就可以记忆化搜索

vector<vector<int>> edge;
vector<vector<int>> graph;
bool dfs(int i, int j) {
    if (graph[i][j] == 1) return true;
    if (graph[i][j] == -1) return false;
    for (auto& e : edge[i]) {
        if (dfs(e, j)) {
            graph[e][j] = 1;
            return true;
        }
    }
    graph[i][j] = -1;
    return false;
}
vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) {
    edge.resize(numCourses);
    graph.resize(numCourses, vector<int>(numCourses));
    for (auto& p : prerequisites) {
        edge[p[0]].push_back(p[1]);
        graph[p[0]][p[1]] = 1;
    }
    vector<bool> res;
    for (auto& q : queries) {
        res.push_back(dfs(q[0], q[1]));
    }
    return res;
}

method 2: Floyd

同样用数组存储两个节点的关系，如果(i,k)和(k,j)都为true，则(i,j)也可以为true

vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) {
    vector<vector<bool>> dp(numCourses, vector<bool>(numCourses, false));
    for (auto& p : prerequisites) {
        dp[p[0]][p[1]] = true;
    }
    for (int k = 0; k < numCourses; k++) {
        for (int i = 0; i < numCourses; i++) {
            for (int j = 0; j < numCourses; j++) {
                dp[i][j] = (dp[i][j] || (dp[i][k] && dp[k][j]));
            }
        }
    }
    vector<bool> res;
    for (auto& q : queries) {
        res.push_back(dp[q[0]][q[1]]);
    }
    return res;
}