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

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

Xshell远程连接Kali(默认 | 私钥)Note版

前言:xshell远程连接&#xff0c;私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

leetcodeSQL解题:3564. 季节性销售分析

leetcodeSQL解题&#xff1a;3564. 季节性销售分析 题目&#xff1a; 表&#xff1a;sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...

OPENCV形态学基础之二腐蚀

一.腐蚀的原理 (图1) 数学表达式&#xff1a;dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一&#xff0c;腐蚀跟膨胀属于反向操作&#xff0c;膨胀是把图像图像变大&#xff0c;而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...

C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)

名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...

「全栈技术解析」推客小程序系统开发:从架构设计到裂变增长的完整解决方案

在移动互联网营销竞争白热化的当下&#xff0c;推客小程序系统凭借其裂变传播、精准营销等特性&#xff0c;成为企业抢占市场的利器。本文将深度解析推客小程序系统开发的核心技术与实现路径&#xff0c;助力开发者打造具有市场竞争力的营销工具。​ 一、系统核心功能架构&…...

通过MicroSip配置自己的freeswitch服务器进行调试记录

之前用docker安装的freeswitch的&#xff0c;启动是正常的&#xff0c; 但用下面的Microsip连接不上 主要原因有可能一下几个 1、通过下面命令可以看 [rootlocalhost default]# docker exec -it freeswitch fs_cli -x "sofia status profile internal"Name …...

微服务通信安全:深入解析mTLS的原理与实践

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、引言&#xff1a;微服务时代的通信安全挑战 随着云原生和微服务架构的普及&#xff0c;服务间的通信安全成为系统设计的核心议题。传统的单体架构中&…...

阿里云Ubuntu 22.04 64位搭建Flask流程(亲测)

cd /home 进入home盘 安装虚拟环境&#xff1a; 1、安装virtualenv pip install virtualenv 2.创建新的虚拟环境&#xff1a; virtualenv myenv 3、激活虚拟环境&#xff08;激活环境可以在当前环境下安装包&#xff09; source myenv/bin/activate 此时&#xff0c;终端…...