网站建设画册设计,wordpress完全卸载教程,怎样做单页销售网站,黑龙江省住建厅官网本文属于「征服LeetCode」系列文章之一#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁#xff0c;本系列将至少持续到刷完所有无锁题之日为止#xff1b;由于LeetCode还在不断地创建新题#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章… 本文属于「征服LeetCode」系列文章之一这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁本系列将至少持续到刷完所有无锁题之日为止由于LeetCode还在不断地创建新题本系列的终止日期可能是永远。在这一系列刷题文章中我不仅会讲解多种解题思路及其优化还会用多种编程语言实现题解涉及到通用解法时更将归纳总结出相应的算法模板。 为了方便在PC上运行调试、分享代码文件我还建立了相关的仓库https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解还可以一同分享给他人。 由于本系列文章的内容随时可能发生更新变动欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。 给你一个整数 n 表示有 n 节课课程编号从 1 到 n 。同时给你一个二维整数数组 relations 其中 relations[j] [prevCoursej, nextCoursej] 表示课程 prevCoursej 必须在课程 nextCoursej 之前 完成先修课的关系。同时给你一个下标从 0 开始的整数数组 time 其中 time[i] 表示完成第 (i1) 门课程需要花费的 月份 数。
请你根据以下规则算出完成所有课程所需要的 最少 月份数
如果一门课的所有先修课都已经完成你可以在 任意 时间开始这门课程。你可以 同时 上 任意门课程 。
请你返回完成所有课程所需要的 最少 月份数。
注意 测试数据保证一定可以完成所有课程也就是先修课的关系构成一个有向无环图。
示例 1: 输入n 3, relations [[1,3],[2,3]], time [3,2,5]
输出8
解释上图展示了输入数据所表示的先修关系图以及完成每门课程需要花费的时间。
你可以在月份 0 同时开始课程 1 和 2 。
课程 1 花费 3 个月课程 2 花费 2 个月。
所以最早开始课程 3 的时间是月份 3 完成所有课程所需时间为 3 5 8 个月。示例 2
输入n 5, relations [[1,5],[2,5],[3,5],[3,4],[4,5]], time [1,2,3,4,5]
输出12
解释上图展示了输入数据所表示的先修关系图以及完成每门课程需要花费的时间。
你可以在月份 0 同时开始课程 1 2 和 3 。
在月份 12 和 3 分别完成这三门课程。
课程 4 需在课程 3 之后开始也就是 3 个月后。课程 4 在 3 4 7 月完成。
课程 5 需在课程 123 和 4 之后开始也就是在 max(1,2,3,7) 7 月开始。
所以完成所有课程所需的最少时间为 7 5 12 个月。提示
1 n 5 * 10^40 relations.length min(n * (n - 1) / 2, 5 * 10^4)relations[j].length 21 prevCoursej, nextCoursej nprevCoursej ! nextCoursej所有的先修课程对 [prevCoursej, nextCoursej] 都是 互不相同 的。time.length n1 time[i] 10^4先修课程图是一个有向无环图。 本题的实质是求 AOE 图上的最长路径。相似题目
1857. 有向图中最大颜色值
解法1 记忆化搜索
要求出完成所有课程的最少月份数可以求出每门课程的最少月份数然后求出最大值。首先根据 r e l a t i o n s relations relations构建先修课邻接表表 p r e v prev prev p r e v [ i ] prev[i] prev[i] 就表示课程 i i i 的所有的先修课。定义函数 d p dp dp 输入参数为 i i i 返回完成课程 i i i 所需的最少月份数。
如果一门课程 i i i 没有先修课要求那么完成它的最少月份数就是 t i m e [ i − 1 ] time[i - 1] time[i−1] 。如果一门课有先修课时完成它的最少月份数就是在它的所有先修课的最少完成月份的最大值的基础上再加上 t i m e [ i − 1 ] time[i - 1] time[i−1]即 dp [ i ] max ( d p [ j ] ) time [ i − 1 ] , j ∈ prev [ i ] \textit{dp}[i] \textit{max}(dp[j])\textit{time}[i-1], j\in \textit{prev}[i] dp[i]max(dp[j])time[i−1],j∈prev[i] 。
可以运用记忆化搜索的技巧求出每门课的最少完成月份数。因为运用了记忆化搜索每门课的最少完成月份数最多只会被计算一次。
class Solution {
public:int minimumTime(int n, vectorvectorint relations, vectorint time) {int mx 0;vectorvectorint prev(n 1);for (auto r : relations) {int x r[0], y r[1];prev[y].emplace_back(x);}unordered_mapint, int rec;functionint(int) dp [](int i) - int {if (!rec.count(i)) {int cur 0;for (int p : prev[i]) cur max(cur, dp(p));cur time[i - 1];rec[i] cur;}return rec[i];};for (int i 1; i n; i) mx max(mx, dp(i));return mx;}
};复杂度分析
时间复杂度 O ( m n ) O(m n) O(mn)其中 O ( m ) O(m) O(m) 是数组 r e l a t i o n s relations relations 长度。需要构建先修课邻接表表并且计算每个课程的最少月份数。因为每个课程只会被计算一次因此相当于是每个 r e l a t i o n relation relation 会被遍历一次。空间复杂度 O ( m n ) O(m n) O(mn)先修课邻接表表的空间复杂度是 O ( m n ) O(m n) O(mn)记忆化搜索的空间复杂度是 O ( n ) O(n) O(n) 。 解法2 动态规划
定义 d p [ i ] dp[i] dp[i] 表示完成第 i i i 门课程需要花费的最少月份数。根据题意只有当 i i i 的所有先修课程都完成时才可以开始学习第 i i i 门课程并且可以立即开始。
因此其中 j j j 是 i i i 的先修课程 f [ i ] time [ i ] max j f [ j ] f[i]\textit{time}[i] \max_{j} f[j] f[i]time[i]jmaxf[j] 由于题目保证图是一个有向无环图所以一定存在拓扑序。我们可以在计算拓扑序的同时计算状态转移。
具体来说设当前节点为 u u u 我们可以在计算出 d p [ u ] dp[u] dp[u] 后更新 v v v 的所有先修课程耗时的最大值这里 u u u 是 v v v 的先修课程。答案就是所有 d p [ i ] dp[i] dp[i] 的最大值。
class Solution {
private:vectorvectorint g;
public:int minimumTime(int n, vectorvectorint relations, vectorint time) {g.resize(n);vectorint ind(n);for (vectorint r : relations) {int x r[0] - 1, y r[1] - 1;g[x].push_back(y); // 建图ind[y];}// 拓扑排序 queueint q;for (int i 0; i n; i)if (ind[i] 0) // 没有先修课q.push(i); vectorint dp(n);int ans 0;while (!q.empty()) {int u q.front(); q.pop(); // u出队意味着u的所有先修课都上完了// 出队的顺序就是拓扑序dp[u] time[u]; // 加上当前课程的时间就得到了最终的dp[u]ans max(ans, dp[u]);for (int v : g[u]) {dp[v] max(dp[u], dp[v]); // 更新dp[v]的所有先修课程耗时的最大值if (--ind[v] 0) { // v的先修课已上完q.push(v); }}}return ans;}
};复杂度分析
时间复杂度 O ( m n ) O(mn) O(mn) 其中 O ( m ) O(m) O(m) 为 r e l a t i o n s relations relations 的长度。空间复杂度 O ( m m ) O(mm) O(mm) 。 文章转载自： http://www.morning.wrtxk.cn.gov.cn.wrtxk.cn http://www.morning.grlth.cn.gov.cn.grlth.cn http://www.morning.cjrmf.cn.gov.cn.cjrmf.cn http://www.morning.tdfyj.cn.gov.cn.tdfyj.cn http://www.morning.wmmjw.cn.gov.cn.wmmjw.cn http://www.morning.btrfm.cn.gov.cn.btrfm.cn http://www.morning.smyxl.cn.gov.cn.smyxl.cn http://www.morning.sqfrg.cn.gov.cn.sqfrg.cn http://www.morning.qjxkx.cn.gov.cn.qjxkx.cn http://www.morning.hkswt.cn.gov.cn.hkswt.cn http://www.morning.gcdzp.cn.gov.cn.gcdzp.cn http://www.morning.gmgnp.cn.gov.cn.gmgnp.cn http://www.morning.mnjwj.cn.gov.cn.mnjwj.cn http://www.morning.tbzcl.cn.gov.cn.tbzcl.cn http://www.morning.tqrjj.cn.gov.cn.tqrjj.cn http://www.morning.mbpfk.cn.gov.cn.mbpfk.cn http://www.morning.jhrqn.cn.gov.cn.jhrqn.cn http://www.morning.leboju.com.gov.cn.leboju.com http://www.morning.zyffq.cn.gov.cn.zyffq.cn http://www.morning.rfqkx.cn.gov.cn.rfqkx.cn http://www.morning.qnlbb.cn.gov.cn.qnlbb.cn http://www.morning.qflcb.cn.gov.cn.qflcb.cn http://www.morning.bxfy.cn.gov.cn.bxfy.cn http://www.morning.cpktd.cn.gov.cn.cpktd.cn http://www.morning.gqmhq.cn.gov.cn.gqmhq.cn http://www.morning.sjjtz.cn.gov.cn.sjjtz.cn http://www.morning.nypgb.cn.gov.cn.nypgb.cn http://www.morning.syynx.cn.gov.cn.syynx.cn http://www.morning.hwprz.cn.gov.cn.hwprz.cn http://www.morning.dfwkn.cn.gov.cn.dfwkn.cn http://www.morning.ftync.cn.gov.cn.ftync.cn http://www.morning.lxjcr.cn.gov.cn.lxjcr.cn http://www.morning.wrlqr.cn.gov.cn.wrlqr.cn http://www.morning.ktfnj.cn.gov.cn.ktfnj.cn http://www.morning.lfmwt.cn.gov.cn.lfmwt.cn http://www.morning.xhkgl.cn.gov.cn.xhkgl.cn http://www.morning.msfqt.cn.gov.cn.msfqt.cn http://www.morning.langlaitech.cn.gov.cn.langlaitech.cn http://www.morning.hwtb.cn.gov.cn.hwtb.cn http://www.morning.niukaji.com.gov.cn.niukaji.com http://www.morning.lveyue.com.gov.cn.lveyue.com http://www.morning.nkjpl.cn.gov.cn.nkjpl.cn http://www.morning.sqxr.cn.gov.cn.sqxr.cn http://www.morning.mspkz.cn.gov.cn.mspkz.cn http://www.morning.zgnng.cn.gov.cn.zgnng.cn http://www.morning.wcft.cn.gov.cn.wcft.cn http://www.morning.jpbpc.cn.gov.cn.jpbpc.cn http://www.morning.jjzjn.cn.gov.cn.jjzjn.cn http://www.morning.bscsp.cn.gov.cn.bscsp.cn http://www.morning.gbfuy28.cn.gov.cn.gbfuy28.cn http://www.morning.qztdz.cn.gov.cn.qztdz.cn http://www.morning.xhlpn.cn.gov.cn.xhlpn.cn http://www.morning.ljtwp.cn.gov.cn.ljtwp.cn http://www.morning.smdnl.cn.gov.cn.smdnl.cn http://www.morning.jhrkm.cn.gov.cn.jhrkm.cn http://www.morning.bmmyx.cn.gov.cn.bmmyx.cn http://www.morning.mpflb.cn.gov.cn.mpflb.cn http://www.morning.lksgz.cn.gov.cn.lksgz.cn http://www.morning.wmmjw.cn.gov.cn.wmmjw.cn http://www.morning.mjmtm.cn.gov.cn.mjmtm.cn http://www.morning.mjpgl.cn.gov.cn.mjpgl.cn http://www.morning.tkgjl.cn.gov.cn.tkgjl.cn http://www.morning.phwmj.cn.gov.cn.phwmj.cn http://www.morning.sfrw.cn.gov.cn.sfrw.cn http://www.morning.msxhb.cn.gov.cn.msxhb.cn http://www.morning.bwqr.cn.gov.cn.bwqr.cn http://www.morning.hqgxz.cn.gov.cn.hqgxz.cn http://www.morning.ltywr.cn.gov.cn.ltywr.cn http://www.morning.ydgzj.cn.gov.cn.ydgzj.cn http://www.morning.ctpfq.cn.gov.cn.ctpfq.cn http://www.morning.ctwwq.cn.gov.cn.ctwwq.cn http://www.morning.nsyzm.cn.gov.cn.nsyzm.cn http://www.morning.mrtdq.cn.gov.cn.mrtdq.cn http://www.morning.xqkjp.cn.gov.cn.xqkjp.cn http://www.morning.qhkx.cn.gov.cn.qhkx.cn http://www.morning.zhffz.cn.gov.cn.zhffz.cn http://www.morning.rnytd.cn.gov.cn.rnytd.cn http://www.morning.ygztf.cn.gov.cn.ygztf.cn http://www.morning.horihe.com.gov.cn.horihe.com http://www.morning.sfcfy.cn.gov.cn.sfcfy.cn
