【面试题】面试官:判断图是否有环?_数据结构复试问题 有向图是否有环
type: 'NODE';name: string;[x: string]: any;
};
[x: string]: any;
};
export type Data = Node | Edge;
复制代码
* 测试数据如下
const data: Data[] = [
{
id: ‘1’,
data: {
type: ‘NODE’,
name: ‘节点1’
}
},
{
id: ‘2’,
data: {
type: ‘NODE’,
name: ‘节点2’
}
},
{
id: ‘3’,
data: {
type: ‘NODE’,
name: ‘节点3’
}
},
{
id: ‘4’,
source: {
cell: ‘1’
},
target: {
cell: ‘2’
},
data: {
type: ‘EDGE’
}
},
{
id: ‘5’,
source: {
cell: ‘1’
},
target: {
cell: ‘3’
},
data: {
type: ‘EDGE’
}
}
];
复制代码
* 根据数据结构和测试数据`data:Data[]`,分为以下几个步骤:1. 获得边的集合和节点的集合。2. 根据边的集合和节点的集合,获得每个节点的有向邻居节点的集合。即以每个节点的为起点,通过边连接的下一个节点的集合。例如测试数据`节点1`,通过边`id4`和边`id5`,可以连接`节点2`和`节点3`,所以`节点1`的邻居节点是`节点2`和`节点3`,而`节点2`和`节点3`无有向邻居节点。3. 最后根据有向邻居节点的集合,判断是否有环。### 具体实现* 获得边的集合和节点的集合
const edges: Map<string, Edge> = new Map(), nodes: Map<string, Node> = new Map();
const idMapTargetNodes: Map<string, Node[]> = new Map();
const initGraph = () => {
for (const item of data) {
const { id } = item;
if (item.data.type === ‘EDGE’) {
edges.set(id, item as Edge);
} else {
nodes.set(id, item as Node);
}
}
};
复制代码
* 获取有向邻居节点的集合,这里的集合,可以优化成`id`。我为了方便处理,存储了节点
const idMapTargetNodes: Map<string, Node[]> = new Map();
const initTargetNodes = () => {
for (const [id, edge] of edges) {
const { source, target } = edge;
const sourceId = source.cell, targetId = target.cell;
if (nodes.has(sourceId) && nodes.has(targetId)) { //防止有空的边,即边的起点和终点不在节点的集合里
const targetNodes = idMapTargetNodes.get(sourceId);
if (Array.isArray(targetNodes)) {
targetNodes.push(nodes.get(targetId) as Node);
} else {
idMapTargetNodes.set(sourceId, [nodes.get(targetId) as Node]);
}
}
}
};
复制代码
* 最后判断是否有环,有两种方式:递归和循环。都是深度优先遍历。`execute`是遍历所有节点,`hasCycle`是把图的某个节点做为起点,判断是否有环。如果以所有节点为起点,都没有环,说明这个图没有环。1. 递归。`hasCycle`判断当前节点是否有环;`checked`是做优化,防止某些节点多次检查,回溯阶段,把当前节点加入`checked`;`visited`记录当前执行的`hasCycle`里是否访问过,如果访问过,就是有环。需要注意的是,每次执行`hasCycle`时,`visited`用的是一个变量,所以在回溯阶段需要把当前节点从`visited`里删除。
const checked: Set = new Set();
const hasCycle = (node: Node, visited: Set) => {
if (checked.has(node.id)) return false;
if (visited.has(node)) return true;
visited.add(node);
const { id } = node;
const targetNodes = idMapTargetNodes.get(id);
if (Array.isArray(targetNodes)) {
for (const item of targetNodes) {
if (hasCycle(item, visited)) return true;
}
}
checked.add(node.id);
visited.delete(node);
return false;
};
const execute = () => {
const visited: Set = new Set();
for (const [id, node] of nodes) {
if (hasCycle(node, visited)) return true;
checked.add(id);
}
return false;
};
复制代码
1. 循环。`checked`和递归时,作用一样,这里不做说明。`visited`是用来判断当前的节点是否遍历过,如果遍历过,就是有环。用循环实现深度优先遍历时,需要用`栈`来存储当前链路上的节点,即当前节点已经后代节点。并且从`栈`里面获取最后一个节点,作为当前遍历的节点。如果当前节点有向邻居节点不为空,就把有向邻居节点的最后一个节点拿出来压栈;如果有向邻居节点为空,就把当前的节点出栈。在压栈时,如果当前节点在`visited`里,就说明有环,如果没有就要把这个节点加入到`visited`。在出栈时,把当前节点从`visited`里删除掉,因为如果不删掉,当一个节点的多个邻居节点最终指向同一个节点时,会判断为有环。
const checked: Set = new Set();
const hasCycle = (node: Node) => {
const { id } = node;
if (checked.has(id)) return false;
const stack = [id];
const visited: Set = new Set();
visited.add(id);
while (stack.length > 0) {
const lastId = stack[stack.length - 1];
const targetNodes = idMapTargetNodes.get(lastId) || [];
if (targetNodes.length > 0) {
最后
前端CSS面试题文档,JavaScript面试题文档,Vue面试题文档,大厂面试题文档


.length > 0) {
最后
前端CSS面试题文档,JavaScript面试题文档,Vue面试题文档,大厂面试题文档
[外链图片转存中…(img-ze1QDx8k-1719237898712)]
[外链图片转存中…(img-pp9ZHRr7-1719237898713)]
相关文章:
【面试题】面试官:判断图是否有环?_数据结构复试问题 有向图是否有环
type: NODE;name: string;[x: string]: any; }; [x: string]: any;}; export type Data Node | Edge; 复制代码 * 测试数据如下const data: Data[] [ { id: ‘1’, data: { type: ‘NODE’, name: ‘节点1’ } }, { id: ‘2’, data: { type: ‘NODE’, name: ‘节点2’ } },…...
办理北京公司注册地址异常变更要求和流程
在北京注册公司时选择注册地址是非常重要的一环,注册地址不仅体现在营业执照上,在网上也有公示信息,一般选用的是商用地址和商住两用地址,在公司经营过程中,因为经营需要变更注册地址,也要依法变更…...
当你在浏览器输入一个地址
你在浏览器中输出了一个地址,回车后,一直到显示页面,中间经历了哪些过程 ? 1. 用户输入 URL 并按下回车 用户在浏览器的地址栏中输入一个 URL(例如 http://example.com)并按下回车键。 2. DNS 解析 浏览…...
JSP基础知识概述
目录 JSP一、什么是JSP1.1 概念1.2 创建JSP1.3 JSP编写Java代码1.4 JSP实现原理 二、JSP与HTML集成2.1 普通脚本2.2 声明脚本2.3 输出脚本2.4 JSP指令2.5 动作标签 三、内置对象3.1 四大域对象 JSP 一、什么是JSP 1.1 概念 简化的Servlet设计,在HTMl标签中嵌套Jav…...
国产编程—— 仓颉
应用 仓颉编程语言是一款由华为主导设计和实现的面向全场景智能的编程语言,主要应用于以下领域: 中文字符编码和文本数据处理:仓颉编程语言充分利用汉字的结构特点来设计编码,为开发者提供了一种高效的方式来编码、存储和处理中…...
0X JavaSE-并发编程(锁)
1...
云计算【第一阶段(18)】磁盘管理与文件系统 分区格式挂载(一)
目录 一、磁盘基础 二、磁盘结构 2.1、机械硬盘 2.2、固态硬盘 2.3、扩展移动硬盘 2.4、机械磁盘的一些计算(了解) 2.5、磁盘接口类型 二、Linux 中使用的文件系统类型 2.1、磁盘分区的表示 2.1.1、主引导记录(MBR) 2.1.2、Linux中将硬盘、分…...
Flask-cache
Flask-cache 目录 Flask-cache基本使用配置可用参数SimpleCacheNullCacheFileSystemCacheRedisCacheRedisSentinelCacheRedisClusterCacheMemcachedCacheSASLMemcachedCacheUWSGICache Flask-Cache是一个强大的缓存库,为基于Flask的应用提供了简单易用的API和多种缓…...
【面试题】面试小技巧:如果有人问你 xxx 技术是什么?_面试问你对什么技术特别了解
前端工程越来越大,前面几种方案不能很好的支持单元测试。 在这样的背景下,React 诞生了。React 带来了新的思维模式,UI fn(props),React 中一个组件就是一个函数或者一个类,一个函数或者一个类就是一个基础单位&…...
简单分享Python语言(发现其实并不难)
一. Python基础 Python是一种解释型语言,这意味着开发者可以在代码被编写后立即执行它们,而无需编译。Python的基本语法简单明了,以下是一些基础知识点: 变量和数据类型:Python支持多种数据类型,包括整型&…...
基于VTK9.3.0+Visual Studio2017 c++实现DICOM影像MPR多平面重建
开源库:VTK9.3.0 开发工具:Visual Studio2017 开发语言:C 实现过程: void initImageActor(double* Matrix, double* center, vtkSmartPointer<vtkImageCast> pImageCast,vtkSmartPointer<vtkImageReslice> imageRe…...
【论文精读】ViM: Out-Of-Distribution with Virtual-logit Matching 使用虚拟分对数匹配的分布外检测
文章目录 一、文章概览(一)问题来源(二)文章的主要工作(三)相关研究 二、动机:Logits 中缺失的信息(一)logits(三)基于零空间的 OOD 评分…...
【面试题】前端 移动端自适应?_前端移动端适配面试题
设备像素比 设备像素比 (DevicePixelRatio) 指的是设备物理像素和逻辑像素的比例 。比如 iPhone6 的 DPR 是2。 设备像素比 物理像素 / 逻辑像素。可通过 window.devicePixelRatio 获取,CSS 媒体查询代码如下 media (-webkit-min-device-pixel-ratio: 3), (min-…...
在Maven工程中手动配置并测试SpringBoot(巨详)
本篇博客承继自博客: 在IDEA 2024.1.3 (Community Edition)中创建Maven项目_idea2024.1.3如何创建maven项目-CSDN博客 配置POM文件 打开工程中的pom.xml文件,先向其中写入 <parent><groupId>org.springframework.boot</groupId><…...
c# 去掉字符串首尾的 特殊符号
如果首尾的 - 数量不确定,可以使用以下方法来去掉字符串两端的 - 字符: 使用正则表达式: using System.Text.RegularExpressions;string input "---Hello, World!---"; string trimmed Regex.Replace(input, "^-*|-*$", ""); // trimmed 为 …...
在容器中共享本地文件
在容器中共享本地文件 目录 卷与绑定挂载的对比在主机和容器之间共享文件Docker 访问主机文件的文件权限试一试 运行一个容器使用绑定挂载在 Docker Dashboard 中访问文件停止容器 额外资源下一步 每个容器都有一切需要运行的资源,而不依赖于主机机器上预先安装的…...
Java Matcher类方法深度剖析:查找和匹配、索引方法
1. 引言 在Java中,正则表达式是处理字符串的强大工具,而java.util.regex包中的Matcher类则是实现这一功能的核心。对于Java工程师而言,熟练掌握Matcher类的使用方法,无疑能够极大地提升字符串处理的效率和准确性。本文将对Matcher类的方法进行深度讲解,并按照查找和匹配方…...
Redis-数据类型-zset
文章目录 1、查看redis是否启动2、通过客户端连接redis3、切换到db4数据库4、将一个或多个member元素及其score值加入到有序集key当中5、升序返回有序集key6、升序返回有序集key,让分数一起和值返回的结果集7、降序返回有序集key,让分数一起和值返回到结…...
手撕RPC——前言
手撕RPC——前言 一、RPC是什么?二、为什么会出现RPC三、RPC的原理3.1 RPC是如何做到透明化远程服务调用?3.2 如何实现传输消息的编解码? 一、RPC是什么? RPC(Remote Procedure Call,远程过程调用ÿ…...
Vite: 关于预构建的毫秒级响应
概述 在我们的项目代码中,我们所说的模块代码其实分为两部分 一部分是源代码,也就是业务代码另一部分是第三方依赖的代码,即 node_modules 中的代码 Vite 是一个提倡 no-bundle 的构建工具,相比于传统的 Webpack能做到开发时的模…...
测试微信模版消息推送
进入“开发接口管理”--“公众平台测试账号”,无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息: 关注测试号:扫二维码关注测试号。 发送模版消息: import requests da…...
conda相比python好处
Conda 作为 Python 的环境和包管理工具,相比原生 Python 生态(如 pip 虚拟环境)有许多独特优势,尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处: 一、一站式环境管理:…...
零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?
一、核心优势:专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发,是一款收费低廉但功能全面的Windows NAS工具,主打“无学习成本部署” 。与其他NAS软件相比,其优势在于: 无需硬件改造:将任意W…...
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...
在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能
下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能,包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...
linux arm系统烧录
1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 (忘了有没有这步了 估计有) 刷机程序 和 镜像 就不提供了。要刷的时…...
DBAPI如何优雅的获取单条数据
API如何优雅的获取单条数据 案例一 对于查询类API,查询的是单条数据,比如根据主键ID查询用户信息,sql如下: select id, name, age from user where id #{id}API默认返回的数据格式是多条的,如下: {&qu…...
GitHub 趋势日报 (2025年06月08日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...
使用 SymPy 进行向量和矩阵的高级操作
在科学计算和工程领域,向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能,能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作,并通过具体…...
用机器学习破解新能源领域的“弃风”难题
音乐发烧友深有体会,玩音乐的本质就是玩电网。火电声音偏暖,水电偏冷,风电偏空旷。至于太阳能发的电,则略显朦胧和单薄。 不知你是否有感觉,近两年家里的音响声音越来越冷,听起来越来越单薄? —…...
