想要精通算法和SQL的成长之路 - 找到最终的安全状态

想要精通算法和SQL的成长之路 - 找到最终的安全状态

  • 前言
  • 一. 找到最终的安全状态
    • 1.1 初始化邻接图
    • 1.2 构建反向邻接图
    • 1.3 BFS遍历
    • 1.4 完整代码

前言

想要精通算法和SQL的成长之路 - 系列导航

一. 找到最终的安全状态

原题链接
在这里插入图片描述

我们从题目中可以看出来:

  • 出度为0的,就是终端节点。
  • 如果存在路径通向终端节点,那么该节点就是安全节点。那么终端节点本身也可以作为安全节点。
  • 而题目要求我们返回的是安全节点。
  • 满足题目要求的节点,一定是和终端节点相连的节点。

思路如下:

  1. 我们构建有向邻接图,并且统计出度。
  2. 出度为0的丢到队列中。
  3. 每层循环,处理出度为0的节点(终端节点),我们反向拿到它的前置节点(因此构建邻接图的时候要反向构建有向邻接图), 更新它的出度。若前置节点的出度为0,说明它之前就是一个安全节点,现在成为了终端节点。
  4. 遍历完毕之后,再遍历一遍出度数组,把所有出度为0的节点更新到结果集中即可。

1.1 初始化邻接图

int n = graph.length;
// 初始化邻接图和出度数组
List<Integer>[] adj = new ArrayList[n];
int[] outDegree = new int[n];
for (int i = 0; i < n; i++) {adj[i] = new ArrayList<>();
}

1.2 构建反向邻接图

// 构建邻接图和出度数组,这里的索引就是一条有向边的起点。
for (int i = 0; i < n; i++) {// 出度的个数,就是二维的长度outDegree[i] = graph[i].length;// 反向构建邻接图for (int j = 0; j < graph[i].length; j++) {adj[graph[i][j]].add(i);}
}

1.3 BFS遍历

// 将出度为0的入队
LinkedList<Integer> queue = new LinkedList<>();
for (int i = 0; i < n; i++) {if (outDegree[i] == 0) {queue.offer(i);}
}
while (!queue.isEmpty()) {int size = queue.size();for (int i = 0; i < size; i++) {Integer cur = queue.poll();// adj[cur] 就是 pre --> 终端节点,拿到的所有 prefor (Integer pre : adj[cur]) {// 出度 -1,若为0,继续入队if (--outDegree[pre] == 0) {queue.offer(pre);}}}
}

1.4 完整代码

public class Test802 {public List<Integer> eventualSafeNodes(int[][] graph) {int n = graph.length;// 初始化邻接图和出度数组List<Integer>[] adj = new ArrayList[n];int[] outDegree = new int[n];for (int i = 0; i < n; i++) {adj[i] = new ArrayList<>();}// 构建邻接图和出度数组,这里的索引就是一条有向边的起点。for (int i = 0; i < n; i++) {// 出度的个数,就是二维的长度outDegree[i] = graph[i].length;// 反向构建邻接图for (int j = 0; j < graph[i].length; j++) {adj[graph[i][j]].add(i);}}// 将出度为0的入队LinkedList<Integer> queue = new LinkedList<>();for (int i = 0; i < n; i++) {if (outDegree[i] == 0) {queue.offer(i);}}while (!queue.isEmpty()) {int size = queue.size();for (int i = 0; i < size; i++) {Integer cur = queue.poll();// adj[cur] 就是 pre --> 终端节点,拿到的所有 prefor (Integer pre : adj[cur]) {// 出度 -1,若为0,继续入队if (--outDegree[pre] == 0) {queue.offer(pre);}}}}// 最终出度为0的全部加入到结果集中ArrayList<Integer> res = new ArrayList<>();for (int i = 0; i < n; i++) {if (outDegree[i] == 0) {res.add(i);}}return res;}
}

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

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

相关文章

面试官:如何理解CDN?说说实现原理?

一、是什么 CDN (全称 Content Delivery Network)&#xff0c;即内容分发网络 构建在现有网络基础之上的智能虚拟网络&#xff0c;依靠部署在各地的边缘服务器&#xff0c;通过中心平台的负载均衡、内容分发、调度等功能模块&#xff0c;使用户就近获取所需内容&#xff0c;降…

大模型技术实践(五)|支持千亿参数模型训练的分布式并行框架

在上一期的大模型技术实践中&#xff0c;我们介绍了增加式方法、选择式方法和重新参数化式方法三种主流的参数高效微调技术&#xff08;PEFT&#xff09;。微调模型可以让模型更适合于我们当前的下游任务&#xff0c;但当模型过大或数据集规模很大时&#xff0c;单个加速器&…

OpenCV中world模块介绍

OpenCV中有很多模块&#xff0c;模块间保持最小的依赖关系&#xff0c;用户可以根据自己的实际需要链接相关的库&#xff0c;而不需链接所有的库&#xff0c;这样在最终交付应用程序时可以减少总库的大小。但如果需要依赖OpenCV的库太多,有时会带来不方便&#xff0c;此时可以使…

忆联分布式数据库存储解决方案,助力MySQL实现高性能、低时延

据艾瑞咨询研究院《2022 年中国数据库研究报告》显示&#xff0c;截止2021年&#xff0c;中国分布式数据库占比达到 20%左右&#xff0c;主要以 MySQL 和 PostgreSQL 为代表的开源数据库为主。MySQL 作为备受欢迎的开源数据库&#xff0c;当前已广泛应用于互联网、金融、交通、…

【C++初阶】类和对象(上)

个人主页点击直达&#xff1a;小白不是程序媛 我的代码仓库&#xff1a;Gitee C系列专栏&#xff1a;C头疼记 目录 前言 面向过程和面向对象的初步认识 类的引入 类的定义 类的两种定义方式&#xff1a; 类的访问限定符及封装 封装 类的作用域 类的实例化 类对象模型…

LVS负载均衡集群 (NAT模式)

LVS集群 集群的概念&#xff1a; 为解决某个特定的问题&#xff0c;将多个计算机组合起来形成一个单个系统 集群的水平扩展&#xff1a; 增加设备&#xff0c;并行运行多个服务&#xff0c;通过网路连接和算法来调度服务分配的问题 集群的类型&#xff1a; 负载均衡集群&#…

【Javascript】基础数据类型

目录 基础数据类型 1.number 字面量声明 数字对象方式声明 整数判断 指定返回小数位数 NaN-表示非数字值 浮点精度 解决误差 String 字面量声明 数字对象声明 连接运算符 获取长度 大小写转换 转换成大写 转换成小写 ​编辑 移除空白 获取单字符 ​编辑 截…

html中公用css、js提取、使用

前言 开发中&#xff0c;页面会有引用相同的css、js的情况&#xff0c;如需更改则每个页面都需要调整&#xff0c;重复性工作较多&#xff0c;另外在更改内容之后上传至服务器中会有缓存问题&#xff0c;特针对该情况对公用css、js进行了提取并对引用时增加了版本号 一、提取…

分布式Trace:横跨几十个分布式组件的慢请求要如何排查?

目录 前言 一、问题的出现&#xff1f; 二、一体化架构中的慢请求排查如何做 三、分布式 Trace原理 四、如何来做分布式 Trace 前言 在分布式服务架构下&#xff0c;一个 Web 请求从网关流入&#xff0c;有可能会调用多个服务对请求进行处理&#xff0c;拿到最终结果。这个…

Redis-Sentinel高可用架构学习

Redis-Sentinel高可用架构 Redis主从复制过程&#xff1a; 主从同步原理 Redis Sentinel&#xff08;哨兵&#xff09;高可用集群方案&#xff1a;Redis-Sentinel是Redis官方推荐的高可用性(HA)解决方案。 当用Redis做Master-slave的高可用方案时&#xff0c;假如master宕机了…

Rust-后端服务调试入坑记

这篇文章收录于Rust 实战专栏。这个专栏中的相关代码来自于我开发的笔记系统。它启动于是2023年的9月14日。相关技术栈目前包括&#xff1a;Rust&#xff0c;Javascript。关注我&#xff0c;我会通过这个项目的开发给大家带来相关实战技术的分享。 如果你关注过我的Rust 实战里…

Unity⭐️Win和Mac安卓打包环境配置

文章目录 🟥 配置Android SDK1️⃣ 配置 SDK Platforms2️⃣ 配置 SDK Tools🎁 Android SDK Build-Tools🎁 Android SDK Command-line Tools(latest)🎁 Android SDK Tools(Obsolete)🟧 配置NDK🟩 配置JDK前情提示: 此方法适用于Windows/Mac 在配置时注意开启 🪜 …

解决osg绘制场景时因Z冲突导致重影或闪烁等不正常情况

目录 1. 问题的提出 2. Z冲突&#xff08;z-fighting&#xff09;简介 2.1. Z冲突&#xff08;z-fighting&#xff09;产生的原因 2.2. 如何消除Z冲突&#xff08;z-fighting&#xff09; 3. 代码实现 1. 问题的提出 今天绘制了一个棋盘格&#xff0c;鼠标在棋盘格上单击…

CVE-2019-0708漏洞实战

使用命令&#xff1a;search 0708搜索exp脚本 搜索网段中主机漏洞 use auxiliary/scanner/rdp/cve_2019_0708_bluekeep 照例&#xff0c;show options 看一下配置 设置网段set RHOSTS x.x.x.x run运行就行了 使用攻击模块 use exploit/windows/rdp/cve_2019_0708_bluekee…

论文阅读-多目标强化学习-envelope MOQ-learning

introduction 一种多目标强化学习算法&#xff0c;来自2019 Nips《A Generalized Algorithm for Multi-Objective Reinforcement Learning and Policy Adaptation》本文引用代码全部来源于论文中的链接。主要参考run_e3c_double.py文件 1 总体思想 1.将输入中加入多目标的偏…

Leetcode 202 快乐数(HashSet,环形链表思想)

Leetcode 202 快乐数&#xff08;HashSet&#xff09; 解法1 &#xff1a; 用HashSet来检测循环:star:为什么说数字n的位数由log n给定呢&#xff1f;解法2 &#xff1a; 链表的思想[出现循环表示链表出现环]&#xff0c;使用快慢指针法 题目链接>>>>>>>&…

用 Java 在 PDF 中创建和管理图层,实现交互式文档

PDF 图层&#xff08;也称为可见图层或附加图层等&#xff09;是组织和管理 PDF 文档中内容可见性的一种方法。PDF 图层可用于创建交互式文档、隐藏或显示特定信息、创建多语言版本文档等。通过添加和删除图层&#xff0c;用户可以根据需要定制 PDF 文档指定内容的可见性与显示…

PO模式在selenium自动化测试框架的优势

大家都知道po模式可以提高代码的可读性和减少了代码的重复&#xff0c;但是相对的缺点还有&#xff0c;今天通过本文一起学习下PO模式在selenium自动化测试框架的优势&#xff0c;需要的朋友可以参考下 PO模式简介 1.什么是PO模式 PO模型是:Page Object Model的简写 页面对象…

国内有哪些做得好的企业协同办公软件

在当今信息化时代&#xff0c;企业协同办公软件成为了提升企业效率和推动协作的重要工具。国内市场涌现出许多优秀的企业协同办公软件&#xff0c;为企业提供了高效、便捷的协同办公解决方案。在本文中&#xff0c;我们将向大家介绍3款在国内好评如潮的企业协同办公软件&#x…

项目知识点总结-过滤器-MD5注册-邮箱登录

&#xff08;1&#xff09;过滤器 使用过滤器验证用户是否登录 /** * Title: NoLoginFilter.java * Package com.qfedu.web.filter * Description: TODO(用一句话描述该文件做什么) * author Feri * date 2018年5月28日 * version V1.0 */ package com.gdsdx…