2023-06-16 LeetCode每日一题(并行课程 II)

这篇具有很好参考价值的文章主要介绍了2023-06-16 LeetCode每日一题(并行课程 II)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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,则表示一个学期学不完,此时需要继续深入讨论。

(6) 采用动态规划的思路,此时dp[(1<<n) - 1]即为最终解。文章来源地址https://www.toymoban.com/news/detail-487436.html

到了这里,关于2023-06-16 LeetCode每日一题(并行课程 II)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 2023-08-10LeetCode每日一题(下降路径最小和 II)

    点击跳转到题目位置 给你一个 n x n 整数矩阵 grid ,请你返回 非零偏移下降路径 数字和的最小值。 非零偏移下降路径 定义为:从 grid 数组中的每一行选择一个数字,且按顺序选出来的数字中,相邻数字不在原数组的同一列。 示例 1: 示例 2: 提示: n == grid.length == grid[i].

    2024年02月13日
    浏览(46)
  • 2023-09-09 LeetCode每日一题(课程表)

    点击跳转到题目位置 你这个学期必须选修 numCourses 门课程,记为 0 到 numCourses - 1 。 在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出,其中 prerequisites[i] = [ai, bi] ,表示如果要学习课程 ai 则 必须 先学习课程 bi 。 例如,先修课程对 [0, 1] 表示:想要学

    2024年02月09日
    浏览(52)
  • 2023-06-17 LeetCode每日一题(分割圆的最少切割次数)

    点击跳转到题目位置 圆内一个 有效切割 ,符合以下二者之一: 该切割是两个端点在圆上的线段,且该线段经过圆心。 该切割是一端在圆心另一端在圆上的线段。 一些有效和无效的切割如下图所示。 给你一个整数 n ,请你返回将圆切割成相等的 n 等分的 最少 切割次数。

    2024年02月09日
    浏览(53)
  • 2023-06-12 LeetCode每日一题(树节点的第 K 个祖先)

    点击跳转到题目位置 给你一棵树,树上有 n 个节点,按从 0 到 n-1 编号。树以父节点数组的形式给出,其中 parent[i] 是节点 i 的父节点。树的根节点是编号为 0 的节点。 树节点的第 k 个祖先节点是从该节点到根节点路径上的第 k 个节点。 实现 TreeAncestor 类: TreeAncestor(int n,

    2024年02月08日
    浏览(103)
  • 2023-09-11 LeetCode每日一题(课程表 III)

    点击跳转到题目位置 这里有 n 门不同的在线课程,按从 1 到 n 编号。给你一个数组 courses ,其中 courses[i] = [durationi, lastDayi] 表示第 i 门课将会 持续 上 durationi 天课,并且必须在不晚于 lastDayi 的时候完成。 你的学期从第 1 天开始。且不能同时修读两门及两门以上的课程。 返

    2024年02月09日
    浏览(39)
  • Leetcode每日一题:1289. 下降路径最小和 II(2023.8.10 C++)

    目录 1289. 下降路径最小和 II 题目描述: 实现代码与解析: 动态规划 原理思路:         给你一个  n x n  整数矩阵  grid  ,请你返回  非零偏移下降路径  数字和的最小值。 非零偏移下降路径  定义为:从  grid  数组中的每一行选择一个数字,且按顺序选出来的数字

    2024年02月13日
    浏览(39)
  • 2023-08-06 LeetCode每日一题(24. 两两交换链表中的节点)

    点击跳转到题目位置 给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。 示例1: 示例2: 示例3: 提示: 链表中节点的数目在范围 [0, 100] 内 0 = Node.val = 100 (1) 使用递归解决问题

    2024年02月14日
    浏览(46)
  • 2023-06-14 LeetCode每日一题(二进制字符串前缀一致的次数)

    点击跳转到题目位置 给你一个长度为 n 、下标从 1 开始的二进制字符串,所有位最开始都是 0 。我们会按步翻转该二进制字符串的所有位(即,将 0 变为 1)。 给你一个下标从 1 开始的整数数组 flips ,其中 flips[i] 表示对应下标 i 的位将会在第 i 步翻转。 二进制字符串 前缀

    2024年02月08日
    浏览(54)
  • 2023-06-02 LeetCode每日一题(统计范围内的元音字符串数)

    点击跳转到题目位置 给你一个下标从 0 开始的字符串数组 words 以及一个二维整数数组 queries 。 每个查询 queries[i] = [li, ri] 会要求我们统计在 words 中下标在 li 到 ri 范围内( 包含 这两个值)并且以元音开头和结尾的字符串的数目。 返回一个整数数组,其中数组的第 i 个元素

    2024年02月07日
    浏览(53)
  • Leetcode每日一题:167. 两数之和 II - 输入有序数组(2023.7.8 C++)

    目录 167. 两数之和 II - 输入有序数组 题目描述: 实现代码与解析: 暴力(超时) 双指针 原理思路: 二分 原理思路:         给你一个下标从  1  开始的整数数组  numbers  ,该数组已按   非递减顺序排列   ,请你从数组中找出满足相加之和等于目标数  target  的两

    2024年02月13日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包