LeetCode刷题.14(不用算法解决1557. 可以到达所有点的最少点数目)

给你一个 有向无环图 , n 个节点编号为 0 到 n-1 ,以及一个边数组 edges ,其中 edges[i] = [fromi, toi] 表示一条从点  fromi 到点 toi 的有向边。

找到最小的点集使得从这些点出发能到达图中所有点。题目保证解存在且唯一。

你可以以任意顺序返回这些节点编号。

示例 1:

输入:n = 6, edges = [[0,1],[0,2],[2,5],[3,4],[4,2]]

输出:[0,3]

解释:从单个节点出发无法到达所有节点。从 0 出发我们可以到达 [0,1,2,5] 。从 3 出发我们可以到达 [3,4,2,5] 。所以我们输出 [0,3] 。

示例 2:

输入:n = 5, edges = [[0,1],[2,1],[3,1],[1,4],[2,4]]

输出:[0,2,3]

解释:注意到节点 0,3 和 2 无法从其他节点到达,所以我们必须将它们包含在结果点集中,这些点都能到达节点 1 和 4 。

提示:

2 <= n <= 10^5

1 <= edges.length <= min(10^5, n * (n - 1) / 2)

edges[i].length == 2

0 <= fromi, toi < n

所有点对 (fromi, toi) 互不相同。

解题思路:

        若一个图中的某一节点没有入度,则说明其它节点访问不到它,那么要遍历所有节点,他必须当第一个出发点,否则无法遍历它,而有入度的总会有节点能访问到,拿示例 1图来说:

        图中打×的表示没有入度的节点,打√的则是有入度的节点

        从节点0出发:0->1        0->2->5

        从节点1出发:1

        从节点2出发:2->5

        从节点3出发:3->4->2->5

        从节点4出发:4->3->5

        从节点5出发:5

        由分析可知:从所有有入度的节点(1,2,4,5)出发只会遍历1,2,4和5,因为入度不为零的点总可以由某个无入度的点到达,所以这些点不包括在最小的合法点集合当中。而从所有无入度节点(0,3)出发则能将节点全部遍历,因此我们只需要返回所有无入度的节点即可。

代码实现:

        1.哈希表记录:

class Solution {
    public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {
        //哈希表记录所有有入度的点
        Set<Integer> hs=new HashSet<>();
        for(int x=0;x<edges.size();x++){
            hs.add(edges.get(x).get(1));
        }
        List<Integer> l=new ArrayList<>();
        //从零遍历,若该节点不在哈希表中说明,它为无入度节点,则存放到l中
        for(int x=0;x<n;x++){
            if(!hs.contains(x)){
                l.add(x);
            }
        }
        return l;
    }
}

        2.运用boolean数组记录:

class Solution {
    public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {
        //运用boolean类型数组存放,若有入度则为true
        boolean []b=new boolean[n];
        for(int x=0;x<edges.size();x++){
            b[edges.get(x).get(1)]=true;
        }
        List<Integer> l=new ArrayList<>();
        //false放进l中
        for(int x=0;x<n;x++){
            if(!b[x]) l.add(x);
        }
        return l;
    }
}

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Python跑pytorch程序抢占公共GPU自动运行脚本

问题描述 当我们有一个服务器&#xff0c;服务器上面有4-5个GPU&#xff0c;那么我们需要时刻看哪个GPU空着&#xff0c;当发现服务器空闲了&#xff0c;我们就可以跑自己的深度学习了。 然而&#xff0c;人盯着总是费时费力的&#xff0c;所以可以让Python看到哪个GPU空闲就…

Windows使用(版本8.11)ElasticSearch、elasticsearch-head、kibana

下载安装引用这篇文章 目录 1、ES基本知识核心术语核心概念倒排索引ES字典树ES怎么保证读写一致 2、Window启动ES步骤elasticsearch-8.11.3elasticsearch-head-masterkibana-8.11.3 3、Kibana 调用ES API示例 1、ES基本知识 核心术语 ● 索引&#xff1a;index &#xff08;相…

centos 7.6 忘记root密码 怎么重置root密码

centos 7.6 忘记root密码 怎么重置root密码 1、 问题描述2、解决方法 1、 问题描述 centos 7.6 忘记root密码&#xff0c;登录不了root用户 2、解决方法 启动系统进入grub界面&#xff0c;按e进入编辑模式&#xff0c;找到含有quiet的这行。在这行最后 添加 rw init/bin/ba…

基础数据结构之堆栈

堆栈的定义、入栈、出栈、查询栈顶 #include <stdio.h> #include <stdlib.h>typedef int DataType;// 定义栈节点结构体 struct StackNode;struct StackNode {DataType data; // 节点数据struct StackNode* next; // 指向下一个节点的指针 };// 定…

Python基础知识:整理12 JSON数据格式的转换

首先导入python中的内置包json import json 1 准备一个列表&#xff0c;列表内每个元素都是字典&#xff0c;将其转换为JSON 使用json.dumps()方法 data [{"name": "John", "age": 30}, {"name": "Jane", "age":…

NAND系统性能提升常见方案

随着NAND的发展&#xff0c;针对NAND系统性能提升&#xff0c;业内目前主要的做法有以下几种方案&#xff1a; 1.提升总线频率和优化AC时序&#xff1a; 提高NAND闪存接口的工作频率可以显著加快数据传输速度。通过不断改进工艺和技术&#xff0c;缩短了信号稳定时间、降低了延…

逆向分析爬取网页动态

本例子以爬取人民邮电出版社网页新书的信息为例 由于页面是动态的&#xff0c;信息会不停地更新&#xff0c;所以不同时间的爬取结果会不同。

Selenium+Remote WebDriver+python脚本访问示例

一、环境要求&#xff1a; 1、selenium-server安装&#xff0c;下载地址&#xff1a;Release Selenium 4.16 SeleniumHQ/selenium GitHub 2、python3及pycharm 二、启动selenium-server 下载selenium-server之后&#xff0c;解压到D:\selenium-server目录&#xff0c;然后…

error: undefined reference to ‘cv::imread(std::__ndk1::basic_string<char

使用android studio编译项目时&#xff0c;由于用到了 cv::imread&#xff08;&#xff09;函数&#xff0c;编译时却报错找不到该函数的定义。 cv::imread一般是在highgui.hpp中定义&#xff0c;因此我加上了该头文件&#xff1a; #include “opencv2/highgui/highgui.hpp” 但…

设计模式之六大设计原则

学习的最大理由是想摆脱平庸&#xff0c;早一天就多一份人生的精彩&#xff1b;迟一天就多一天平庸的困扰。各位小伙伴&#xff0c;如果您&#xff1a; 想系统/深入学习某技术知识点… 一个人摸索学习很难坚持&#xff0c;想组团高效学习… 想写博客但无从下手&#xff0c;急需…

Hive 数据同步

一、需求 同步集团的数据到断直连环境。 二、思路 三、同步数据&#xff08;方案&#xff09; 1、环境&#xff1a;断直连模拟环境 2、操作机器&#xff1a;ETL 机器 XX.14.36.216 3、工作路径&#xff1a;cd /usr/local/fqlhadoop/hadoop/bin 4、执行命令&#xff1a; 命令…

GIS真的是天坑专业吗?

是&#xff0c;也不是。 首先说是&#xff0c;GIS到底坑在哪&#xff1f; 1、专业定位不清晰&#xff0c;具有很强的误导性 听过很多学生抱怨&#xff0c;关于GIS专业&#xff0c;大家觉得最坑的地方&#xff0c;在于一开始在选专业的时候&#xff0c;以为这个专业跟计算机专…

如何判断 vite 的运行环境是开发模式还是生产模式 production? development?

如何判断 vite 的运行环境是开发模式还是生产模式 production&#xff1f; development&#xff1f; vite 有两种获取当前运行环境模式的方法&#xff1a; 官方说明&#xff1a; 完整说明地址&#xff1a; https://cn.vitejs.dev/guide/env-and-mode.html#node-env-and-modes…

【LangChain学习之旅】—(6) 提示工程(下):用思维链和思维树提升模型思考质量

【LangChain学习之旅】—&#xff08;6&#xff09; 提示工程&#xff08;下&#xff09;&#xff1a;用思维链和思维树提升模型思考质量 什么是 Chain of ThoughtFew-Shot CoTZero-Shot CoTChain of Thought 实战CoT 的模板设计程序的完整框架Tree of Thought总结 Reference&a…

一阶低通滤波器

一阶低通滤波器 X为输入&#xff0c;Y为滤波后得到的输出值&#xff1b;本次的输出结果主要取决于上次的滤波输出值&#xff0c;其中a是和滤波效果有关的一个参数&#xff0c;称为滤波系数&#xff1b;它决定新采样值在本次滤波结果中所占的权重&#xff1b; 滤波系数a越小&a…

AI绘画软件Stable Diffusion模型/Lora/VAE文件存放位置

型下载说明&#xff08;下载模型后输入对应参数即可生成&#xff09; 建议直接去civitai.com找模型&#xff0c;如果无法找到可以在幕后模型区找也可以去&#xff0c; 下载好后放入对应的文件夹。进入127.0.0.1:7680 左上角刷新即可看到新的模型。 模型种类 大模型 大模型特…

揭秘人工智能:探索智慧未来

&#x1f308;个人主页&#xff1a;聆风吟 &#x1f525;系列专栏&#xff1a;数据结构、网络奇遇记 &#x1f516;少年有梦不应止于心动&#xff0c;更要付诸行动。 文章目录 &#x1f4cb;前言一. 什么是人工智能?二. 人工智能的关键技术2.1 机器学习2.2 深度学习2.1 计算机…

【一文详解】知识分享:(C#开发学习快速入门)

面向对象(OOP) c语言是面向过程。 c是面向过程面向对象。 c#是纯粹的面向对象: 核心思想是以人的思维习惯来分析和解决问题。万物皆对象。 面向对象开发步骤: 分析对象 特征行为关系(对象关系/类关系) 写代码: 特征–>成员变量 方法–>成员方法 实例化–具体对象 …

一本数学教材严谨和通俗哪个更重要?

一本教材也许无法同时兼顾严谨和通俗&#xff0c;而且在不同的场景下&#xff0c;严谨和通俗的重要性也不尽相同&#xff1a; 在正式的学术场合&#xff0c;严谨当然重要&#xff0c;一些不严谨的教材可能无法通过审校&#xff0c;在读者存在疑问的时候&#xff0c;也不一定能给…

揭露欧拉骗局4.“Σ1/n²=π²/6”里的猫腻

自然数平方倒数求和Σ1/n是一个并不复杂的问题&#xff0c;但它困扰了欧洲大陆整整90年&#xff0c;在欧系数学里它被称为“巴塞尔级数”。 解决巴塞尔级数让欧拉一战成名&#xff0c;然而欧拉采用的方法对数学这门学问是严重的侮辱。数学是工具学科&#xff0c;数学的宗旨是化…