当前位置: 首页 > 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…...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

Day131 | 灵神 | 回溯算法 | 子集型 子集

Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 笔者写过很多次这道题了&#xff0c;不想写题解了&#xff0c;大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具

文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

linux 下常用变更-8

1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行&#xff0c;YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID&#xff1a; YW3…...

【C语言练习】080. 使用C语言实现简单的数据库操作

080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

ardupilot 开发环境eclipse 中import 缺少C++

目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)

升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点&#xff0c;但无自动故障转移能力&#xff0c;Master宕机后需人工切换&#xff0c;期间消息可能无法读取。Slave仅存储数据&#xff0c;无法主动升级为Master响应请求&#xff…...

3-11单元格区域边界定位(End属性)学习笔记

返回一个Range 对象&#xff0c;只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意&#xff1a;它移动的位置必须是相连的有内容的单元格…...