2023-06-16每日一题
一、题目编号
1494. 并行课程 II
二、题目链接
点击跳转到题目位置
三、题目描述
给你一个整数 n 表示某所大学里课程的数目,编号为 1 到 n ,数组 relations 中, relations[i] = [xi, yi] 表示一个先修课的关系,也就是课程 xi 必须在课程 yi 之前上。同时你还有一个整数 k 。
在一个学期中,你 最多 可以同时上 k 门课,前提是这些课的先修课在之前的学期里已经上过了。
请你返回上完所有课最少需要多少个学期。题目保证一定存在一种上完所有课的方式。
提示:
- 1 <= n <= 15
- 1 <= k <= n
- 0 <= relations.length <= n * (n-1) / 2
- relations[i].length == 2
- 1 <= xi, yi <= n
- xi != yi
- 所有先修关系都是不同的,也就是说 relations[i] != relations[j] 。
- 题目输入的图是个有向无环图。
四、解题代码
class Solution {
public:
int minNumberOfSemesters(int n, vector<vector<int>>& relations, int k) {
vector<int> dp(1 << n, INT_MAX);
vector<int> need(1 << n, 0);
for(int i = 0; i < relations.size(); ++i){
int x = relations[i][0];
int y = relations[i][1];
need[1 << (x - 1)] |= (1 << (y-1));
}
dp[0] = 0;
for(int i = 1; i < (1 << n); ++i){
need[i] = need[i & (i - 1)] | need[i & (-i)];//求出学完i所表示的所有课程所需要的课程位
if ((need[i] | i) != i) {
continue;
}
int valid = i ^ need[i]; // 当前学期可以进行学习的课程集合
if (__builtin_popcount(valid) <= k) {
dp[i] = min(dp[i], dp[i ^ valid] + 1);
} else {
for (int t = valid; t > 0; t = (t - 1) & valid) {
if (__builtin_popcount(t) <= k) {
dp[i] = min(dp[i], dp[i ^ t] + 1);
}
}
}
}
return dp[(1 << n) - 1];
}
};
五、解题思路
(1) 用二进制的方式来表示课程。例如11111(B)表示第1~5门课需要学习。
(2) 首先先求出每门课的先导课情况
(3) 然后继续遍历,从1遍历到(1<<n) - 1,每当遍历到数字i,首先先要求出need[i]想要达成该状态所需要求的课程状况。
(4) 如果所需要的课程已经超出了状态i则跳过不予讨论,即该情况无法达到。
(5) 如果所需要的课程未超过状态x,则判断这学期所能学完的课程为多少,如果小于等于k则可以一个学期学完,如果大于k,则表示一个学期学不完,此时需要继续深入讨论。文章来源:https://www.toymoban.com/news/detail-487436.html
(6) 采用动态规划的思路,此时dp[(1<<n) - 1]即为最终解。文章来源地址https://www.toymoban.com/news/detail-487436.html
到了这里,关于2023-06-16 LeetCode每日一题(并行课程 II)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!