算法day32

第一题

207. 课程表

步骤一:

        通过下图的课程数组,首先画出DAG图(有向无环图)

步骤二:

        其次我们按照DAG图,来构建该图的拓扑排序,等有效的点都按照规则排完序后,观察是否有剩下的点的入度不为0;

步骤三:

        使用数组的结构来存放每一个点的入度;

        我们通过创建队列来存储拓扑排序,首先遍历所有的点,将入度为0的点入队列,这时候进行这个点的bfs,即扫描其他的点。如果被扫描的点和该点有连接,则被扫描的点的入度减去一,同时此时被扫描的点的如度为零的话,就将这个点添加到队列中,进行下一个点的扫描;

        重复上述步骤,直到完成所有队列中的点的bfs,此时判断是否存在一个点的入度不为0来返回数值;

        建图的概念:

        方法一:hash表;如下图所示,使用邻接表来存储图的构造,我们采用hash表来完成这一邻接表的结构;下图第一行表示,0节点后面并列连着1,2,3;

        所以edges表示两个节点之间的连接; key里面存放的是每一个点,valueb表示该节点所连接的点的集合;

方法二:

        链表嵌套链表;

        edges.get(0),表示0号节点;

        edges.get(0).get(3),表示0号节点和3号节点之间的连接;

       

至此,代码如下:

class Solution {public boolean canFinish(int n, int[][] p) {//1\准备工作int[] in = new int[n];//每一个顶点的入度Map<Integer,List<Integer>> edges = new HashMap<>();//链接表存图//2\建图for(int i = 0;i < p.length;i++){int a = p[i][0],b = p[i][1];//b->aif(!edges.containsKey(b)){edges.put(b,new ArrayList<>());}edges.get(b).add(a);in[a]++;}//3、拓扑排序Queue<Integer> q = new LinkedList<>();//3.1 首先把度为0的点假入到队列中for(int i = 0;i < n;i++){if(in[i] == 0) q.add(i);}//3.2 bfswhile(!q.isEmpty()){int t = q.poll();for(int a : edges.getOrDefault(t,new ArrayList<>())){in[a] --;if(in[a] == 0) q.add(a);}}//4\判断是都有环for(int x : in){if(x != 0) return false;}return true;}
}

代码详解:

第二题

210. 课程表 II

        题解如上题故事,这次我们采用链表嵌套链表的方式来创建图,即完成点与点之间的连接,至此,代码如下:

class Solution {public int[] findOrder(int n, int[][] p) {//1、准备工作List<List<Integer>> edges = new ArrayList<>();for(int i = 0;i < n; i++){edges.add(new ArrayList<>());}int[] in = new int[n];//2、建图for(int i = 0; i<p.length;i++){int a = p[i][0], b = p[i][1];//b->aedges.get(b).add(a);in[a]++;}//3、拓扑排序Queue<Integer> q = new LinkedList<>();for(int i = 0; i<n;i++){if(in[i] == 0) q.add(i);}int[] ret = new int[n];int idex = 0;while(!q.isEmpty()){int t = q.poll();ret[idex++] = t;for(int a : edges.get(t)){in[a]--;if(in[a] == 0) q.add(a);}}//4、判断if(idex == n) return ret;else return new int[0];}
}

第三题

LCR 114. 火星词典

至此,代码如下:

class Solution {Map<Character,Set<Character>> edges = new HashMap<>();//邻接表Map<Character,Integer> in = new HashMap<>();//统计入度hash表boolean check;//主要是防止边界即一个为空一个不为空public String alienOrder(String[] words) {//1\初始化入度信息(哈希表)+建图for(String s :words){for(int i = 0; i< s.length();i++){char ch = s.charAt(i);in.put(ch,0);}}int n = words.length;for(int i = 0;i < n;i++){for(int j = i+1;j < n;j++){add(words[i] , words[j]);if(check == true) return "";}}//2、拓扑排序Queue<Character> q = new LinkedList<>();for(char ch : in.keySet()){if(in.get(ch) == 0) q.add(ch);}StringBuffer ret = new StringBuffer();while(!q.isEmpty()){char t = q.poll();ret.append(t);if(!edges.containsKey(t)) continue;for(char ch : edges.get(t)){in.put(ch,in.get(ch) - 1);if(in.get(ch) == 0) q.add(ch);}}//3、判断for(char ch : in.keySet()){if(in.get(ch) != 0) return "";}return ret.toString();   }public void add(String s1,String s2){int n = Math.min(s1.length(),s2.length());int i = 0;for( ; i < n; i++){char c1 = s1.charAt(i);char c2 = s2.charAt(i);if(c1 != c2){//c1 -> c2if(!edges.containsKey(c1)){edges.put(c1,new HashSet<>());}if(!edges.get(c1).contains(c2)){edges.get(c1).add(c2);in.put(c2,in.get(c2) +1);}break;}}if(i == s2.length() && i < s1.length()) check = true;}
}

ps:本次的内容就到这里结束了,如果对你有所帮助的话,就请一键三连哦!!!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/350649.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

解决linux jenkins要求JDK版本与项目版本JDK不一致问题

背景–问题描述&#xff1a; 新入职公司&#xff0c;交接人说jenkins运行有问题&#xff0c;现在都是手动发布&#xff0c;具体原因让我自己看&#xff08;笑哭&#xff09;。我人都蒙了&#xff0c;测试环境都手动发布&#xff0c;那不是麻烦的要死&#xff01; 接手后&am…

养猫发现猫毛过敏?宠物空气净化器真的能拯救猫毛过敏吗?

广东省 猫咪是许多人梦寐以求的伴侣&#xff0c;但对于轻度猫毛过敏和鼻炎患者来说&#xff0c;养猫似乎是个遥不可及的梦想。我常在社交媒体上羡慕地观看朋友们的吸猫日常&#xff0c;却因过敏无法亲自养猫。这种遗憾驱使我寻找解决方案&#xff0c;从研究低过敏猫种到尝试空气…

洗地机哪款好?洗地机十大名牌排行榜

随着科技的发展&#xff0c;各种家居清洁工具层出不穷&#xff0c;为我们的生活带来了诸多便利。在众多清洁工具中&#xff0c;洗地机的清洁效果更受大家喜爱&#xff0c;它能够完美解决了扫地机无法做到的干湿垃圾“一遍清洁”效果&#xff0c;而且几乎能解决日常生活中所有的…

基于springboot实现交通管理在线服务系统项目【项目源码+论文说明】计算机毕业设计

基于springboot实现交通管理在线服务系统演示 摘要 传统办法管理信息首先需要花费的时间比较多&#xff0c;其次数据出错率比较高&#xff0c;而且对错误的数据进行更改也比较困难&#xff0c;最后&#xff0c;检索数据费事费力。因此&#xff0c;在计算机上安装交通管理在线服…

❤ npm运行打包报错归纳

❤ 前端运行打包报错归纳 &#xff08;安装依赖&#xff09;Cannot read property ‘pickAlgorithm’ of null" npm uninstall //删除项目下的node_modules文件夹 npm cache clear --force //清除缓存后 npm install //重新安装 备用安装方式 npm install with --for…

调试了一下午,终于把tailwindcss搞进Blazor了

在Vue和Uniapp项目中使用tailwindcss后&#xff0c;实在是太香了&#xff0c;非常符合我这从XAML走过来的老程序员的手感&#xff0c;所以老想着在Blazor项目中引入。看了几个老外大佬的视频&#xff0c;调试了一下午&#xff0c;终于是捣鼓成功了。由于咱们Blazor项目不在node…

【Arthas案例】某应用依赖两个GAV不同但包含两个相同全限定类名StaticLoggerBinder,引起log4j.Level类找不到异常

3分钟内解决问题 两个不同的GAV依赖冲突&#xff0c;包含相同全限定类名&#xff0c;引起ClassNotFoundException Maven依赖的三坐标体系GAV(G-groupId&#xff0c;A-artifactId&#xff0c;V-version) 【案例1】某应用依赖两个GAV不同的jar&#xff0c;但包含两个相同全限定类…

java安装并配置环境

安装前请确保本机没有java的残留&#xff0c;否则将会安装报错 1.安装java jdk&#xff1a;安装路径Java Downloads | Oracle 中国 百度网盘链接&#xff1a;https://pan.baidu.com/s/11-3f2QEquIG3JYw4syklmQ 提取码&#xff1a;518e 2.双击 按照流程直接点击下一步&#x…

Json-server 的使用教程

目录 前言一、简介二、安装与配置1. 安装 node-js2. npm 镜像设置3. 安装 json-server 三、使用1. 创建本地数据源2. 启动 Json Server3. 操作数据&#xff08;1&#xff09;查询数据&#xff08;2&#xff09;新增数据&#xff08;3&#xff09;修改数据&#xff08;4&#xf…

理解Es的DSL语法(二):聚合

前一篇已经系统介绍过查询语法&#xff0c;详细可直接看上一篇文章&#xff08;理解DSL语法&#xff08;一&#xff09;&#xff09;&#xff0c;本篇主要介绍DSL中的另一部分&#xff1a;聚合 理解Es中的聚合 虽然Elasticsearch 是一个基于 Lucene 的搜索引擎&#xff0c;但…

SpringCloud跨服务远程调用

随着项目的使用者越来越多&#xff0c;项目承担的压力也会越来越大&#xff0c;为了让我们的项目能服务更多的使用者&#xff0c;我们不得不需要把我们的单体项目拆分成多个微服务&#xff0c;就比如把一个商城系统拆分成用户系统&#xff0c;商品系统&#xff0c;订单系统&…

C++笔记之一个函数多个返回值的方法、std::pair、std::tuple、std::tie的用法

C++笔记之一个函数多个返回值的方法、std::pair、std::tuple、std::tie的用法 —— 2024-06-08 杭州 code review! 文章目录 C++笔记之一个函数多个返回值的方法、std::pair、std::tuple、std::tie的用法一.从一个函数中获取多个返回值的方法1. 使用结构体或类2. 使用`std::t…

一文了解Spark引擎的优势及应用场景

Spark引擎诞生的背景 Spark的发展历程可以追溯到2009年&#xff0c;由加州大学伯克利分校的AMPLab研究团队发起。成为Apache软件基金会的孵化项目后&#xff0c;于2012年发布了第一个稳定版本。 以下是Spark的主要发展里程碑&#xff1a; 初始版本发布&#xff1a;2010年开发…

希亦、添可、石头洗地机哪款好用?2024洗地机深度测评

今年的洗地机市场竞争异常激烈&#xff0c;各大品牌纷纷推出了自己的旗舰产品。这对消费者来说是个好消息&#xff0c;因为有更多的选择空间。然而&#xff0c;面对如此多的优质洗地机&#xff0c;选择合适的一款也成了一种“幸福的烦恼”。 作为一个专业的测评人士&#xff0…

【电路笔记】-共集极放大器

共集极放大器 文章目录 共集极放大器1、概述2、等效电路3、电压增益4、偏置方法5、输入阻抗6、输出阻抗7、电流增益8、示例:共集电极放大器的电压、电流和功率增益9、达林顿对10、总结1、概述 本文介绍另一种用于放大信号的双极晶体管架构,通常称为共集电极放大器 (CCA)。 C…

【SpringBoot集成Spring Security】

一、前言 Spring Security 和 Apache Shiro 都是安全框架&#xff0c;为Java应用程序提供身份认证和授权。 二者区别 Spring Security&#xff1a;重量级安全框架Apache Shiro&#xff1a;轻量级安全框架 关于shiro的权限认证与授权可参考小编的另外一篇文章 &#xff1a; …

【AIGC】MetaGPT原理以及应用

目录 MetaGPT原理 MetaGPT应用 MetaGPT和传统编程语言相比有什么优势和劣势 视频中的PPT 参考资料 MetaGPT原理 MetaGPT是一种多智能体框架&#xff0c;它结合了元编程技术&#xff0c;通过标准化操作程序&#xff08;SOPs&#xff09;来协调基于大语言模型的多智能体系统…

qmt量化交易策略小白学习笔记第32期【qmt编程之获取行业概念数据--如何获取迅投行业成分股数据】

qmt编程之获取迅投行业成分股数据 qmt更加详细的教程方法&#xff0c;会持续慢慢梳理。 也可找寻博主的历史文章&#xff0c;搜索关键词查看解决方案 &#xff01; 感谢关注&#xff0c;咨询免费开通量化回测与获取实盘权限&#xff0c;欢迎和博主联系&#xff01; 获取迅投…

2024全新仿麻豆视频苹果cms源码v10影视模板

下载地址&#xff1a;2024全新仿麻豆视频苹果cms源码v10影视模板 高端大气的设计&#xff0c;适合做电影、连续剧、综艺、动漫、微电影、纪录片、海外剧等视频网站

黑马es学习

es 0. 基础概念0.1 倒排索引0.2 文档、索引0.3 与mysql对比 1 基本操作1.1 mapping 索引库操作1.2 单个文档CRUD 3. DSL查询3.1 查询所有3.2 全文检索3.3 精确查询3.4 复合查询-相关性得分3.5 分页3.6 高亮3.7 总结 2. RestClient4. aggs聚合4.1 bucket&#xff08;分桶&#x…