Leetcode力扣秋招刷题路-0802
从0开始的秋招刷题路,记录下所刷每道题的题解,帮助自己回顾总结
802. 找到最终的安全状态
有一个有 n 个节点的有向图,节点按 0 到 n - 1 编号。图由一个 索引从 0 开始 的 2D 整数数组 graph表示, graph[i]是与节点 i 相邻的节点的整数数组,这意味着从节点 i 到 graph[i]中的每个节点都有一条边。
如果一个节点没有连出的有向边,则它是 终端节点 。如果没有出边,则节点为终端节点。如果从该节点开始的所有可能路径都通向 终端节点 ,则该节点为 安全节点 。
返回一个由图中所有 安全节点 组成的数组作为答案。答案数组中的元素应当按 升序 排列。
示例 1:

输入:graph = [[1,2],[2,3],[5],[0],[5],[],[]]
输出:[2,4,5,6]
解释:示意图如上。
节点 5 和节点 6 是终端节点,因为它们都没有出边。
从节点 2、4、5 和 6 开始的所有路径都指向节点 5 或 6 。
示例 2:
输入:graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]]
输出:[4]
解释:
只有节点 4 是终端节点,从节点 4 开始的所有路径都通向节点 4 。
提示:
n == graph.length
1 <= n <= 1 0 4 10^4 104
0 <= graph[i].length <= n
0 <= graph[i][j] <= n - 1
graph[i] 按严格递增顺序排列。
图中可能包含自环。
图中边的数目在范围 [1, 4 ∗ 1 0 4 4 * 10^4 4∗104] 内。
解题思路
拓扑的解法中,所有出度为0的点是安全的,那么出到这些点的点也可以减去这条边,如果其剩下的出度为0,它也是安全的,以此类推。
搜索的时候可以标记节点的当前状态,如果他有出口,暂定为1,如果他的出口全部为安全的点,他们的和必然为0,就认定它也是安全的,否则它是不安全的。
代码
拓扑
class Solution {public List<Integer> eventualSafeNodes(int[][] graph) {int n = graph.length;int[] out = new int[n];Map<Integer, List<Integer>> edges = new HashMap<>();for(int i=0;i<n;i++)for(int j:graph[i]){List<Integer> cur = edges.getOrDefault(j, new ArrayList<>());cur.add(i);edges.put(j, cur);out[i]++;}Deque<Integer> queue = new LinkedList<>();for(int i=0;i<n;i++)if(out[i]==0)queue.add(i);List<Integer> ans = new ArrayList<>();while(queue.size()>0){int node = queue.pollFirst();ans.add(node);if(edges.containsKey(node))for(int nxt: edges.get(node)){out[nxt]--;if(out[nxt] == 0)queue.add(nxt);}}Collections.sort(ans);return ans;}
}
DFS
class Solution {int[][] graph_;int[] states;public List<Integer> eventualSafeNodes(int[][] graph) {int n = graph.length;// 每个点可能的状态: -1:点是未走过的, 0:点是安全的,1:点是走过的不确定安不安全,2:点是不安全的states = new int[n];Arrays.fill(states, -1);graph_ = graph;List<Integer> ans = new ArrayList<>();for(int i=0;i<n;i++)if(dfs(i)==0)ans.add(i);return ans;}public int dfs(int node){if(states[node] == -1){states[node] = 1;for(int nxt:graph_[node]){states[node] += dfs(nxt);if(states[node] > 1)break;}if(states[node] == 1)states[node] = 0;elsestates[node] = 2;}return states[node];}
}
DFS也可以使用纯boolean来标记
class Solution {int[][] graph_;Map<Integer,Boolean> states;public List<Integer> eventualSafeNodes(int[][] graph) {int n = graph.length;graph_ = graph;states = new HashMap<>();List<Integer> ans = new ArrayList<>();for(int i=0;i<n;i++){if(safe(i))ans.add(i);}return ans;}public boolean safe(int node){if(!states.containsKey(node)){states.put(node, false);boolean allTrue = true;for(int nxt: graph_[node])if(!safe(nxt)){allTrue = false;break;}states.put(node, allTrue);}return states.get(node);}
}
相关文章:
Leetcode力扣秋招刷题路-0802
从0开始的秋招刷题路,记录下所刷每道题的题解,帮助自己回顾总结 802. 找到最终的安全状态 有一个有 n 个节点的有向图,节点按 0 到 n - 1 编号。图由一个 索引从 0 开始 的 2D 整数数组 graph表示, graph[i]是与节点 i 相邻的节…...
编程中最难的就是命名?这几招教你快速上手
作者:陈立(勤仁) 你可不能像给狗狗取名字那样给类、方法、变量命名。仅仅因为它很可爱或者听上去不错。 在写代码的时候,你要经常想着,那个最终维护你代码的人可能将是一个有暴力倾向的疯子,并且他还知道你住在哪里。 01 为什么…...
NUXT规范及常见问题
props中不要使用Web环境才有的对象,服务端渲染的时候会失败 使用<Nuxt/>组件代替<router-view/>,使用<NuxtLink/>代替<router-link/>static目录下的资源是静态资源,不应该通过import或../static/img/logo.png等方式…...
2023年Q1天猫空调品牌销量排行榜
如今,空调的普及水平较高,空调行业进入存量换新为主的发展阶段。 根据鲸参谋数据分析平台的相关数据显示,2023年Q1在天猫平台上,空调的销量将近100万件,销售额将近30亿,同时,空调产品的产品均价…...
如何在比特币系统内创造人工生命
信息来源:coingeek.com 自2015年以来,关于比特币能否进行复杂计算以及比特币是否“图灵完备”的争论一直在持续。不幸的是,现在存在着一种流传甚广的谬论,有人说比特币并非图灵完备的,它不能像以太坊区块链那样进行复杂…...
除了Figma,再给你介绍10款好用的协同设计软件
组织结构越来越复杂,团队中的每个人都有独特的技能、经验和专业知识。我们怎样才能让团队更好地合作?在这种情况下,协同设计应运而生。 UI的未来是协同设计!如果你想把握未来的设计趋势,不妨从使用高效的协同设计软件…...
信息安全复习五:数据加密标准(DES)
一、本章梗概 1.主要内容:分组密码、分组密码用到的关键技术和结构、对称密钥密码典型算法DES 2.思考问题: ①按照明文被处理的形式,DES属于标准的分组密码 ②根据密钥的使用数量,DES属于标准的对称密码 3.内容回顾: …...
Java ---包装类
(一)包装类概念 官方说法: Java是面向对象的语言,但是为了便于开发者的使用,Java中却沿用了C语言的基本数据类型,在进行基本的数据计算时,开发者可以直接使用基础类。但是当需要和Java其他对象…...
Baumer工业相机中偏振相机如何使用Baumer堡盟GAPI SDK来进行偏振数据的计算转换输出(C#)
项目场景 Baumer工业相机堡盟相机是一种高性能、高质量的工业相机,可用于各种应用场景,如物体检测、计数和识别、运动分析和图像处理。 Baumer的万兆网相机拥有出色的图像处理性能,可以实时传输高分辨率图像。此外,该相机还具…...
MSVC(Microsoft Visual C++) 中运行库的链接方式MD和MT的区别
问题描述 MSVC(Microsoft Visual C) 中运行库的链接方式MD和MT的区别 问题解答 在MSVC编译器中,运行库(Runtime Library)有两种链接方式:MD(Multithread-DLL)和MT(Multithread)。这两种链接方式的主要区…...
设计模式之解释器模式(C++)
作者:翟天保Steven 版权声明:著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处 一、解释器模式是什么? 解释器模式是一种行为型的软件设计模式,定义了一个解释器,来解释给定语…...
基于MATLAB编程的粒子群算法优化BP神经网络风电功率预测,基于PSO-BP的风电功率预测
目录 摘要 BP神经网络的原理 BP神经网络的定义 BP神经网络的基本结构 BP神经网络的神经元 BP神经网络的激活函数, BP神经网络的传递函数 粒子群算法的原理及步骤 基于粒子群算法改进优化BP神经网络的风电功率 matlab代码 代写下载链接:https://download.csdn.net/download/a…...
开心档之C++ 字符串
C 字符串 目录 C 字符串 C 风格字符串 实例 实例 C 中的 String 类 实例 C 提供了以下两种类型的字符串表示形式: C 风格字符串C 引入的 string 类类型 C 风格字符串 C 风格的字符串起源于 C 语言,并在 C 中继续得到支持。字符串实际上是使用 …...
Java Collection源码分析(JDk corretto 11)
文章目录 Collection 系列源码分析 (JDK Amazon corretto 11)Collection接口Iterable接口 子接口 QueueQueue的子接口 Deque双端队列 子接口ListArrayList 实现类序列化与反序列化(后续解决)获取Calss对象的方式 主要有三种:Arrays工具类System类 LinkedList实现类t…...
13种权重的计算方法
权重计算方法有很多种,不同的方法有不同的特点和适用情况。AHP层次分析法和熵值法在权重计算中属于比较常用的方法。除此之外,还有一些与权重计算相关的方法,今天一文总结了13种与权重计算相关的方法,大家可以对比选择使用。 一、…...
Devops和Gitops区别
一. 什么是devops DevOps 是一种开发(Dev)和运维(Ops)之间协作和沟通的文化、流程和工具的实践方法。它强调迭代、快速交付和持续集成/持续交付,旨在加速软件交付的速度、质量和稳定性。 DevOps 的核心目标是通过自动…...
拿下多家车企定点!4D毫米波雷达「域」系统首发出道
从1R、2R、3R到整车360感知方案,毫米波雷达的前装市场需求量依然保持着快速增长的态势。 高工智能汽车研究院监测数据显示,2022年中国市场(不含进出口)前装标配搭载ADAS毫米波雷达(前向后向盲区)交付1795.…...
【FATE联邦学习】FATE联邦学习使用GPU、指定cuda下标
问题 FATE框架1.x支持GPU训练吗? 寻找 先看了官网,搜官网,发现还是有的。 打开第一个后,里面可以用training param指定各个client的训练GPU,但是好像都是在large language model的。 而在文档中搜寻到的gpu…...
英文数字表达
1基数词 0 nought;zero;O 1 one 2 two 3 three 4 four 5 five 6 six 7 seven 8 eight 9 nine 10 ten 11 eleven 12 twelve 13 thirteen 14 fourteen 15 fifteen 16 sixteen 17 seventeen 18 eighteen 19 nineteen 20 twenty21 twenty-one 22 twenty-two 23 twenty-three 30 th…...
第11届蓝桥杯省赛真题剖析-2020年6月21日Scratch编程初中级组
[导读]:超平老师的《Scratch蓝桥杯真题解析100讲》已经全部完成,后续会不定期解读蓝桥杯真题,这是Scratch蓝桥杯真题解析第125讲。 第11届蓝桥杯省赛,这是2020年6月21日举办的省赛Scratch考试真题,原定于2020年3月7日…...
Java 语言特性(面试系列2)
一、SQL 基础 1. 复杂查询 (1)连接查询(JOIN) 内连接(INNER JOIN):返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...
突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合
强化学习(Reinforcement Learning, RL)是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程,然后使用强化学习的Actor-Critic机制(中文译作“知行互动”机制),逐步迭代求解…...
R语言AI模型部署方案:精准离线运行详解
R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...
Day131 | 灵神 | 回溯算法 | 子集型 子集
Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣(LeetCode) 思路: 笔者写过很多次这道题了,不想写题解了,大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...
无法与IP建立连接,未能下载VSCode服务器
如题,在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈,发现是VSCode版本自动更新惹的祸!!! 在VSCode的帮助->关于这里发现前几天VSCode自动更新了,我的版本号变成了1.100.3 才导致了远程连接出…...
解锁数据库简洁之道:FastAPI与SQLModel实战指南
在构建现代Web应用程序时,与数据库的交互无疑是核心环节。虽然传统的数据库操作方式(如直接编写SQL语句与psycopg2交互)赋予了我们精细的控制权,但在面对日益复杂的业务逻辑和快速迭代的需求时,这种方式的开发效率和可…...
GitHub 趋势日报 (2025年06月08日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...
sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!
简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求,并检查收到的响应。它以以下模式之一…...
08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险
C#入门系列【类的基本概念】:开启编程世界的奇妙冒险 嘿,各位编程小白探险家!欢迎来到 C# 的奇幻大陆!今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类!别害怕,跟着我,保准让你轻松搞…...
MySQL 主从同步异常处理
阅读原文:https://www.xiaozaoshu.top/articles/mysql-m-s-update-pk MySQL 做双主,遇到的这个错误: Could not execute Update_rows event on table ... Error_code: 1032是 MySQL 主从复制时的经典错误之一,通常表示ÿ…...
