当前位置: 首页 > news >正文

算法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:本次的内容就到这里结束了,如果对你有所帮助的话,就请一键三连哦!!!

相关文章:

算法day32

第一题 207. 课程表 步骤一&#xff1a; 通过下图的课程数组,首先画出DAG图&#xff08;有向无环图&#xff09; 步骤二&#xff1a; 其次我们按照DAG图&#xff0c;来构建该图的拓扑排序&#xff0c;等有效的点都按照规则排完序后&#xff0c;观察是否有剩下的点的入度不为0&…...

【QT】信号与槽

目录 概述 Q_OBJECT 自定义信号 自定义槽 带参数的信号和槽 信号与槽断开 定义槽函数时&#xff0c;使用lambda表达式 概述 所谓的信号槽&#xff0c;要解决的问题&#xff0c;就是响应用户的操作&#xff0c;这是QT与其他GUI开发框架比较不同的地方。其他的GUI开发框…...

【Java】解决Java报错:IllegalArgumentException

文章目录 引言1. 错误详解2. 常见的出错场景2.1 非法的参数值2.2 空值或 null 参数2.3 非法的数组索引 3. 解决方案3.1 参数验证3.2 使用自定义异常3.3 使用Java标准库中的 Objects 类 4. 预防措施4.1 编写防御性代码4.2 使用注解和检查工具4.3 单元测试 结语 引言 在Java编程…...

完美的移动端 UI 风格让客户无可挑剔

完美的移动端 UI 风格让客户无可挑剔...

【React】在 React 组件中,怎么使用useContext

在React中,useContext 是一个Hook,它允许你无需显式地通过组件树的每一层来传递 props,就能将值深入到组件树的任何位置。要使用 useContext,你需要先创建一个 Context 对象,然后使用这个对象提供的 Provider 组件来包裹你的应用中的一部分。然后,任何在这个 Provider 下…...

【数据结构】栈的应用

目录 0 引言 1 栈在括号匹配中的应用 2 栈在表达式求值中的应用 2.1 算数表达式 2.2 中缀表达式转后缀表达式 2.3 后缀表达式求值 3 栈在递归中的应用 3.1 栈在函数调用中的作用 3.2 栈在函数调用中的工作原理 4 总结 0 引言 栈&#xff08;Stack&#xff09;是一…...

Opencv基本操作

Opencv基本操作 导入并使用opencv进行图像与视频的基本处理 opencv读取的格式是BGR import cv2 #opencv读取的格式是BGR import numpy import matplotlib.pyplot as plt %matplotlib inline图像读取 通过cv2.imread()来加载指定位置的图像信息。 img cv2.imread(./res/ca…...

2779. 数组的最大美丽值

简单翻译一下题目意思&#xff1a; 对于每个 nums[i] 都可以被替换成 [nums[i]-k, nums[i]k] 区间中的任何数&#xff0c;区间左右是闭的。在每个数字可以替换的前提下&#xff0c;返回数组中最多的重复数字的数量。 第一想法是用一个哈希表&#xff0c;Key 是可以被替换的数…...

数据库修复实例(航线修复)

修复目标 修复回音群岛 (Echo Isles) 到 赞达拉港 (Port of Zandalar) 的航线 SET TRANSPORT_GUID : 32; SET TRANSPORT_ENTRY : 272677; SET CGUID : 850000;-- Adjust transports DELETE FROM transports WHERE guid TRANSPORT_GUID; INSERT INTO transports (guid, entry…...

视频网站下载利器yt-dlp参数详解

yt-dlp 是一个强大的命令行工具&#xff0c;用来下载 YouTube 和其他网站上的视频和音频。它拥有丰富的参数&#xff0c;可以定制下载行为&#xff0c;满足各种需求。本文将详细介绍 yt-dlp 的参数使用。 一、基本参数 -f, –format FORMAT: 指定下载格式&#xff0c;可以用视…...

可解析PHP的反弹shell方法

这里拿vulnhub-DC-8靶场反弹shell&#xff0c;详情见Vulnhub-DC-8 命令执行 拿nc举例 <?php echo system($_POST[cmd]); ?>利用是hackbar&#xff0c;POST提交cmdnc -e /bin/sh 192.168.20.128 6666, 直接反弹shell到kali。 一句话木马 <?php eval($_POST[&qu…...

AMSR-MODIS 边界层水汽 L3 每日 1 度 x 1 度 V1、V2 版本数据集

AMSR-MODIS Boundary Layer Water Vapor L3 Daily 1 degree x 1 degree V1 (AMDBLWV) at GES DISC AMSR-MODIS Boundary Layer Water Vapor L3 Daily 1 degree x 1 degree V2 (AMDBLWV) at GES DISC 简介 该数据集可估算均匀云层下的海洋边界层水汽。AMSR-E 和 AMSR-2 的微波…...

Oracle备份失败处理,看这一篇就够了!

作者&#xff1a;IT邦德 中国DBA联盟(ACDU)成员&#xff0c;10余年DBA工作经验&#xff0c; Oracle、PostgreSQL ACE CSDN博客专家及B站知名UP主&#xff0c;全网粉丝10万 擅长主流Oracle、MySQL、PG、高斯及Greenplum备份恢复&#xff0c; 安装迁移&#xff0c;性能优化、故障…...

后端中缓存的作用以及基于Spring框架演示实现缓存

缓存的作用及演示 现在我们使用的程序都是通过去数据库里拿数据然后展示的 长期对数据库进行数据访问 这样数据库的压力会越来越大 数据库扛不住了 创建了一个新的区域 程序访问去缓存 缓存区数据库 缓存里放数据 有效降低数据访问的压力 我们首先进行一个演示 为了演示…...

Python:基础爬虫

Python爬虫学习&#xff08;网络爬虫&#xff08;又称为网页蜘蛛&#xff0c;网络机器人&#xff0c;在FOAF社区中间&#xff0c;更经常的称为网页追逐者&#xff09;&#xff0c;是一种按照一定的规则&#xff0c;自动地抓取万维网信息的程序或者脚本。另外一些不常使用的名字…...

机器人运动学笔记

一、建模 参考资料&#xff1a;https://zhuanlan.zhihu.com/p/137960186 1、三维模型和连杆、关节定义 2、设置z轴 SDH和MDH会不一样&#xff0c;主要的区别在于SDH中坐标系在连杆末端&#xff0c;MDH中坐标系在连杆首端。虽然这里只是给出z轴&#xff0c;但是由于后面原点位…...

webshell三巨头 综合分析(蚁剑,冰蝎,哥斯拉)

考点: 蚁剑,冰蝎,哥斯拉流量解密 存在3个shell 过滤器 http.request.full_uri contains "shell1.php" or http.response_for.uri contains "shell1.php" POST请求存在明文传输 ant 一般蚁剑执行命令 用垃圾字符在最开头填充 去掉垃圾字符直到可以正常bas…...

stm32MP135裸机编程:启动流程分析

0 参考资料 轻松使用STM32MP13x - 如MCU般在cortex A核上裸跑应用程序.pdf STM32MP135AD数据手册.pdf1 stm32MP135裸机启动流程分析 1.1 启动方式 stm32MP135支持8种启动方式&#xff1a; 注&#xff1a; UART和USB启动并不是指通过UART/USB加载程序&#xff0c;而是通过UA…...

在Pycharm使用Github Copilot

文章目录 1.GitHub Copilot 是什么2.注册GitHub Copilot3.官方使用文档4.安装 GitHub Copilot插件5.在Pycharm中使用6.相关功能键7.启用或禁用 GitHub Copilot 1.GitHub Copilot 是什么 GitHub Copilot 是一款 AI 编码助手&#xff0c;可帮助你更快、更省力地编写代码&#xff…...

Docker镜像构建:Ubuntu18.04+python3.10

1、编写 Dockerfile # 使用Ubuntu 18.04作为基础镜像 FROM ubuntu:18.04RUN apt-get update && apt-get install -y \build-essential \curl \zlib1g-dev \libssl-dev \&& rm -rf /var/lib/apt/lists/*ENV PYTHON_VERSION3.10.8RUN curl -O https://www.pytho…...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)

2025年能源电力系统与流体力学国际会议&#xff08;EPSFD 2025&#xff09;将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会&#xff0c;EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

HTML 列表、表格、表单

1 列表标签 作用&#xff1a;布局内容排列整齐的区域 列表分类&#xff1a;无序列表、有序列表、定义列表。 例如&#xff1a; 1.1 无序列表 标签&#xff1a;ul 嵌套 li&#xff0c;ul是无序列表&#xff0c;li是列表条目。 注意事项&#xff1a; ul 标签里面只能包裹 li…...

C# 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

C++使用 new 来创建动态数组

问题&#xff1a; 不能使用变量定义数组大小 原因&#xff1a; 这是因为数组在内存中是连续存储的&#xff0c;编译器需要在编译阶段就确定数组的大小&#xff0c;以便正确地分配内存空间。如果允许使用变量来定义数组的大小&#xff0c;那么编译器就无法在编译时确定数组的大…...

【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)

前言&#xff1a; 双亲委派机制对于面试这块来说非常重要&#xff0c;在实际开发中也是经常遇见需要打破双亲委派的需求&#xff0c;今天我们一起来探索一下什么是双亲委派机制&#xff0c;在此之前我们先介绍一下类的加载器。 目录 ​编辑 前言&#xff1a; 类加载器 1. …...

【Elasticsearch】Elasticsearch 在大数据生态圈的地位 实践经验

Elasticsearch 在大数据生态圈的地位 & 实践经验 1.Elasticsearch 的优势1.1 Elasticsearch 解决的核心问题1.1.1 传统方案的短板1.1.2 Elasticsearch 的解决方案 1.2 与大数据组件的对比优势1.3 关键优势技术支撑1.4 Elasticsearch 的竞品1.4.1 全文搜索领域1.4.2 日志分析…...

6️⃣Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙

Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙 一、前言:离区块链还有多远? 区块链听起来可能遥不可及,似乎是只有密码学专家和资深工程师才能涉足的领域。但事实上,构建一个区块链的核心并不复杂,尤其当你已经掌握了一门系统编程语言,比如 Go。 要真正理解区…...

Xcode 16 集成 cocoapods 报错

基于 Xcode 16 新建工程项目&#xff0c;集成 cocoapods 执行 pod init 报错 ### Error RuntimeError - PBXGroup attempted to initialize an object with unknown ISA PBXFileSystemSynchronizedRootGroup from attributes: {"isa">"PBXFileSystemSynchro…...

门静脉高压——表现

一、门静脉高压表现 00:01 1. 门静脉构成 00:13 组成结构&#xff1a;由肠系膜上静脉和脾静脉汇合构成&#xff0c;是肝脏血液供应的主要来源。淤血后果&#xff1a;门静脉淤血会同时导致脾静脉和肠系膜上静脉淤血&#xff0c;引发后续系列症状。 2. 脾大和脾功能亢进 00:46 …...