想要精通算法和SQL的成长之路 - 受限条件下可到达节点的数目

想要精通算法和SQL的成长之路 - 受限条件下可到达节点的数目

  • 前言
  • 一. 相交链表(邻接图和DFS)

前言

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

一. 相交链表(邻接图和DFS)

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

public int reachableNodes(int n, int[][] edges, int[] restricted) {
}

我们读一下题目,我们总结几个核心的点:

  1. 无向图。
  2. 受限节点。
  3. 题目用一个二维数组代表图。

针对第一个点和第三个点:我们用何种方式通过二维数组来构建出一个无向图?

使用邻接图。在Java当中,邻接图可以用下面一个模板来完成:

List<Integer>[] adj = new List[n];
// 初始化每个数组
for (int i = 0; i < n; i++) {adj[i] = new ArrayList<>();
}
for (int[] edge : edges) {adj[前继节点].add(后继节点);
}

那么由于本题目又特意声明了它是一个无向图,我们前后顺序换一下再存储一次即可:

adj[前继节点].add(后继节点);
adj[后继节点].add(前继节点);

针对第二点:受限节点。我们用一个一维数组,代表每个元素是否受限,下标即是对应的元素值:

boolean[] limits = new boolean[n];
for (int i : restricted) {limits[i] = true;
}

有了这些数据,我们就可以通过DFS去递归遍历这颗树:

  1. 我们指定对应的元素 0 作为根节点,向后继节点递归。
  2. 同时因为无向的关系,我们在递归节点的时候,需要做判断,当前节点并不是父节点,满足条件才可往深层递归。否则就会出现死循环。

例如:以上图的案例,最终的无向图数据部分如下:

  • 0–>1,4,5。
  • 1->0,1,3

死循环逻辑如下:

  • 第一层:倘若当前节点为1的时候,根据顺序深层递归。递归节点0。
  • 第二层:当前遍历节点为0,发现0的相邻节点有1,开始递归节点1。回到第一步。
  • 第三层…

因此我们在dfs递归的时候需要有两个参数:

  1. 当前节点。
  2. 当前节点的父节点。

同时我们用一个全局变量count代表递归的数量(即是题目返回要求)

void dfs(int root, int pre) {count++;for (int node : adj[root]) {if (!limits[node] && node != pre) {dfs(node, root);}}
}

最终完整代码如下:

public class Test2368 {int count = 0;List<Integer>[] adj;boolean[] limits;public int reachableNodes(int n, int[][] edges, int[] restricted) {// 邻接图数据构建adj = new List[n];for (int i = 0; i < n; i++) {adj[i] = new ArrayList<>();}for (int[] edge : edges) {adj[edge[0]].add(edge[1]);adj[edge[1]].add(edge[0]);}// 构建受限节点数组limits = new boolean[n];for (int i : restricted) {limits[i] = true;}// 开始递归,从根节点0开始,父节点不存在,我们传一个-1dfs(0, -1);return count;}void dfs(int root, int pre) {count++;// adj[root] 就是与 当前节点 所有的相邻节点for (int node : adj[root]) {// 非受限节点并且当前节点并不是父节点的时候,继续往下递归if (!limits[node] && node != pre) {dfs(node, root);}}}
}

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

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

相关文章

Linux下Minio分布式存储安装配置(图文详细)

文章目录 Linux下Minio分布式存储安装配置(图文详细)1 资源准备1.1 创建存储目录1.2 获取Minio Server资源1.3 获取Minio Client资源 2 Minio Server安装配置2.1 切换目录2.2 后台启动2.3 查看进程2.4 控制台测试 3 Minio Client安装配置3.1 切换目录3.2 移动mc脚本3.2 运行mc命…

LeetCode 39. Combination Sum【回溯,剪枝】中等

本文属于「征服LeetCode」系列文章之一&#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁&#xff0c;本系列将至少持续到刷完所有无锁题之日为止&#xff1b;由于LeetCode还在不断地创建新题&#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章…

cudnn-windows-x86_64-8.6.0.163_cuda11-archive 下载

网址不太好访问的话,请从下面我提供的分享下载 Download cuDNN v8.6.0 (October 3rd, 2022), for CUDA 11.x 此资源适配 cuda11.x 将bin和include文件夹里的文件&#xff0c;分别复制到C盘安装CUDA目录的对应文件夹里 安装cuda时自动设置了 CUDA_PATH_V11_8 及path C:\Progra…

数据结构——排序算法——快速排序

快速排序算法的基本思想是 1.从数组中取出一个数&#xff0c;称之为基数&#xff08;pivot&#xff09; 2.遍历数组&#xff0c;将比基数大的数字放到它的右边&#xff0c;比基数小的数字放到它的左边。遍历完成后&#xff0c;数组被分成了左右两个区域 3.将左右两个区域视为两…

leecode 每日一题 2596. 检查骑士巡视方案

2596. 检查骑士巡视方案 骑士在一张 n x n 的棋盘上巡视。在 有效 的巡视方案中&#xff0c;骑士会从棋盘的 左上角 出发&#xff0c;并且访问棋盘上的每个格子 恰好一次 。 给你一个 n x n 的整数矩阵 grid &#xff0c;由范围 [0, n * n - 1] 内的不同整数组成&#xff0c;其…

记录selenium和chrome使用socks代理打开网页以及查看selenium的版本

使用前&#xff0c;首先打开socks5全局代理。 之前我还写过一篇关于编程中使用到代理的情况&#xff1a; 记录一下python编程中需要使用代理的解决方法_python 使用全局代理_小小爬虾的博客-CSDN博客 在本文中&#xff0c;首先安装selenium和安装chrome浏览器。 参考我的文章…

vue中实现瀑布流布局

父组件 <template><WaterfallFlow :list"list"/> </template><script setup lang"ts">import WaterfallFlow from "/components/WaterfallFlow.vue"; import {reactive} from "vue"; type listType {height…

向量范数及其Python代码

【向量范数】 向量由于既有大小又有方向&#xff0c;所以不能直接比较大小。 向量范数通过将向量转化为实数&#xff0c;然后进行向量的大小比较。 所以&#xff0c;向量范数是用于度量“向量大小”的量。 设向量 &#xff0c;则有&#xff1a; ● 向量的 范数&#xff1a; ●…

C语言入门Day_19 初识函数

目录 1.函数的定义 2.函数的调用 3.易错点 4.思维导图 前言&#xff1a; printf()我们已经很熟悉了&#xff0c;它有一个特定的功能&#xff0c;就是在屏幕上输出一行文字。之前的课程我们都称呼printf()为一个功能&#xff0c;实际上ta在编程中有个特定的名字——函数。 …

嵌入式学习笔记(28)按键和CPU的中断系统

按键的物理特性 (1)、平时没人按的时候&#xff0c;弹簧把按键按钮弹开。此时内部断开的。 (2)、有人按下的时候&#xff0c;手的力量克服弹簧的弹力&#xff0c;将按钮按下&#xff0c;此时内部保持接通&#xff08;闭合&#xff09;状态&#xff1b;如果手拿开&#xff0c;…

VSCode 安装使用教程 环境安装配置 保姆级教程

一个好用的 IDE 不仅能提升我们的开发效率&#xff0c;还能让我们保持愉悦的心情&#xff0c;这样才是非常 Nice 的状态 ^_^ 那么&#xff0c;什么是 IDE 呢 &#xff1f; what IDE&#xff08;Integrated Development Environment&#xff0c;集成开发环境&#xff09;是含代码…

线性代数的本质(十)——矩阵分解

文章目录 矩阵分解LU分解QR分解特征值分解奇异值分解奇异值分解矩阵的基本子空间奇异值分解的性质矩阵的外积展开式 矩阵分解 矩阵的因式分解是把矩阵表示为多个矩阵的乘积&#xff0c;这种结构更便于理解和计算。 LU分解 设 A A A 是 m n m\times n mn 矩阵&#xff0c;…

论文阅读 - Outlier detection in social networks leveraging community structure

目录 摘要 1. Introduction 2. Related works 3. Preliminaries 3.1. 模块化度量 3.2. Classes of outliers 3.2.1. 点异常 3.2.2. Contextual anomalies 3.2.3. Collective anomalies 3.3. Problem definition 3.4. Outliers score 4. Methodology 4.1. Proposed appr…

86 # express 基本实现

koa 和 express 的区别 koa 内部原理使用 es6 来编写的&#xff08;promise async await&#xff09;&#xff0c;express 是使用 es5 来编写的&#xff0c;内部是基于回调函数来实现express 内置了很多中间件&#xff08;功能会比 koa 强大一些&#xff0c;内部集成了路由&a…

OPENCV--实现meanshift图像分割

Meanshift原理 效果图 API # -*- coding:utf-8 -*- """ 作者:794919561 日期:2023/9/13 """ import cv2 import numpy as npimg = cv2.imread("F:\\learnOpenCV\\openCVLearning\\pictures\\Lena.jpg

过拟合、欠拟合、泛化误差、训练误差

模型容量的影响&#xff1a; 泛化误差&#xff1a; 当训练的模型的容量过了最优点时&#xff0c;泛化误差反而升高&#xff0c;这是由于模型过于关注细节导致&#xff0c;模型也同时记住噪声&#xff1b;当拿来一个真的数据时&#xff0c;模型会被一些无关紧要的细节所干扰。 …

ASP.NET dotnet 3.5 实验室信息管理系统LIMS源码

技术架构&#xff1a;ASP.NET dotnet 3.5 LIMS作为一个信息管理系统&#xff0c;它有着和ERP、MIS之类管理软件的共性&#xff0c;如它是通过现代管理模式与计算机管理信息系统支持企业或单位合理、系统地管理经营与生产&#xff0c;最大限度地发挥现有设备、资源、人、技术的…

27.EI文章复现《高比例清洁能源接入下计及需求响应的配电网重构》

下载地址&#xff1a;高比例清洁能源接入下计及需求响应的配电网重构 1主要内容 该程序复现《高比例清洁能源接入下计及需求响应的配电网重构》&#xff0c;以考虑网损成本、弃风弃光成本和开关操作惩罚成本的综合成本最小为目标&#xff0c;针对配电网重构模型的非凸性&…

PyTorch实战-实现神经网络图像分类基础Tensor最全操作详解(一)

目录 前言 一、PyTorch数据结构-Tensor 1.什么是Tensor 2.数据Tensor使用场景 3.张量形态 标量&#xff08;0D 张量&#xff09; 向量&#xff08;1D 张量&#xff09; 矩阵(2D张量) 3D 张量与高维张量 二、Tensor的创建 1. 从列表或NumPy数组创建 2. 使用特定的初始…

5.10.WebRTC接口宏

那今天呢&#xff1f;我给大家介绍一下web rtc的接口宏&#xff0c;那之所以在现成的章节中要介绍接口宏。是由于接口在调用的过程中啊&#xff0c;会发生线程的切换&#xff0c;所以把接口宏这部分知识我们放在线程这一章还算比较合适的。 那另外呢&#xff0c;我们对于接口…