2023-07-28 LeetCode每日一题(并行课程 III)

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

2023-07-28每日一题

一、题目编号

2050. 并行课程 III

二、题目链接

点击跳转到题目位置

三、题目描述

给你一个整数 n ,表示有 n 节课,课程编号从 1 到 n 。同时给你一个二维整数数组 relations ,其中 relations[j] = [prevCoursej, nextCoursej] ,表示课程 prevCoursej 必须在课程 nextCoursej之前 完成(先修课的关系)。同时给你一个下标从 0 开始的整数数组 time ,其中 time[i] 表示完成第 (i+1) 门课程需要花费的 月份 数。

请你根据以下规则算出完成所有课程所需要的 最少 月份数:

  • 如果一门课的所有先修课都已经完成,你可以在 任意 时间开始这门课程。
    你可以 同时任意门课程
  • 请你返回完成所有课程所需要的 最少 月份数。

**注意:**测试数据保证一定可以完成所有课程(也就是先修课的关系构成一个有向无环图)。

提示:

  • 1 <= n <= 5 * 104
  • 0 <= relations.length <= min(n * (n - 1) / 2, 5 * 104)
  • relations[j].length == 2
  • 1 <= prevCoursej, nextCoursej <= n
  • prevCoursej != nextCoursej
  • 所有的先修课程对 [prevCoursej, nextCoursej] 都是 互不相同 的。
  • time.length == n
  • 1 <= time[i] <= 104
  • 先修课程图是一个有向无环图。

示例1:
2023-07-28 LeetCode每日一题(并行课程 III),LeetCode每日一题,leetcode,算法,数据结构

示例2:
2023-07-28 LeetCode每日一题(并行课程 III),LeetCode每日一题,leetcode,算法,数据结构

四、解题代码

class Solution {
public:
    int minimumTime(int n, vector<vector<int>>& relations, vector<int>& time) {
        int mx = 0;
        vector<vector<int>> prev(n + 1);
        for (auto &relation : relations) {
            int x = relation[0], y = relation[1];
            prev[y].emplace_back(x);
        }
        unordered_map<int, int> memo;
        function<int(int)> dp = [&](int i) -> int {
            if (!memo.count(i)) {
                int cur = 0;
                for (int p : prev[i]) {
                    cur = max(cur, dp(p));
                }
                cur += time[i - 1];
                memo[i] = cur;
            }
            return memo[i];
        };

        for (int i = 1; i <= n; i++) {
            mx = max(mx, dp(i));
        }
        return mx;
    }
};

五、解题思路

(1) 使用记忆化搜索来解决问题。文章来源地址https://www.toymoban.com/news/detail-616656.html

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

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

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

相关文章

  • 2023-07-07 LeetCode每日一题(过桥的时间)

    点击跳转到题目位置 共有 k 位工人计划将 n 个箱子从旧仓库移动到新仓库。给你两个整数 n 和 k,以及一个二维整数数组 time ,数组的大小为 k x 4 ,其中 time[i] = [leftToRighti, pickOldi, rightToLefti, putNewi] 。 一条河将两座仓库分隔,只能通过一座桥通行。旧仓库位于河的右岸,新仓

    2024年02月15日
    浏览(37)
  • 2023-08-28 LeetCode每日一题(插入区间)

    点击跳转到题目位置 给你一个 无重叠的 ,按照区间起始端点排序的区间列表。 在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。 示例 1: 示例 2: 示例 3: 示例 4: 示例 5: 提示: 0 = intervals.length = 10 4 interval

    2024年02月11日
    浏览(46)
  • 2023-07-31 LeetCode每日一题(重排链表)

    点击跳转到题目位置 给定一个单链表 L 的头节点 head ,单链表 L 表示为: 请将其重新排列后变为: 不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。 示例 1: 示例 2: 提示: 链表的长度范围为 [1, 5 * 10 4 ] 1 = node.val = 1000 (1) 使用 分治 的思路来解决问题。

    2024年02月14日
    浏览(45)
  • 2023-07-08 LeetCode每日一题(三数之和)

    点击跳转到题目位置 给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请 你返回所有和为 0 且不重复的三元组。 **注意:**答案中不可以包含重复的三元组。 提示: 3 = nums.length = 3000 -10 5

    2024年02月13日
    浏览(49)
  • 2023-07-29 LeetCode每日一题(环形链表)

    点击跳转到题目位置 给你一个链表的头节点 head ,判断链表中是否有环。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:p

    2024年02月15日
    浏览(39)
  • 2023-07-15 LeetCode每日一题(四数之和)

    点击跳转到题目位置 给你一个由 n 个整数组成的数组 nums ,和一个目标值 target 。请你找出并返回满足下述全部条件且 不重复 的四元组 [nums[a], nums[b], nums[c], nums[d]] (若两个四元组元素一一对应,则认为两个四元组重复): 0 = a, b, c, d n a、b、c 和 d 互不相同 nums[a] + nums[b]

    2024年02月16日
    浏览(45)
  • 2023-07-13 LeetCode每日一题(下降路径最小和)

    点击跳转到题目位置 给你一个 n x n 的 方形 整数数组 matrix ,请你找出并返回通过 matrix 的 下降路径 的 最小和 。 下降路径 可以从第一行中的任何元素开始,并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列(即位于正下方或者沿对角线向左

    2024年02月15日
    浏览(77)
  • 2023-07-30 LeetCode每日一题(环形链表 II)

    点击跳转到题目位置 给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链

    2024年02月15日
    浏览(59)
  • 2023/07/02_leetcode每日一题_2.两数相加

    给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。 请你将两个数相加,并以相同形式返回一个表示和的链表。 你可以假设除了数字 0 之外,这两个数都不会以 0 开头。 示例: 输入:l1 = [9,9,9,9,9,9

    2024年02月11日
    浏览(48)
  • 2023/07/01_leetcode每日一题_1. 两数之和

    给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。 一开始审错题了,还以

    2024年02月12日
    浏览(47)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包