当前位置：首页 > news >正文

LeetCode算法题(Go语言实现)_45

news 来源：原创 2025/9/6 7:27:07

题目

n 座城市，从 0 到 n-1 编号，其间共有 n-1 条路线。因此，要想在两座不同城市之间旅行只有唯一一条路线可供选择（路线网形成一颗树）。去年，交通运输部决定重新规划路线，以改变交通拥堵的状况。
路线用 connections 表示，其中 connections[i] = [a, b] 表示从城市 a 到 b 的一条有向路线。
今年，城市 0 将会举办一场大型比赛，很多游客都想前往城市 0 。
请你帮助重新规划路线方向，使每个城市都可以访问城市 0 。返回需要变更方向的最小路线数。
题目数据保证每个城市在重新规划路线方向后都能到达城市 0 。

一、代码实现（BFS邻接表法）

func minReorder(n int, connections [][]int) int {adj := make([][][2]int, n) // [邻接节点，方向标记]for _, conn := range connections {a, b := conn[0], conn[1]adj[a] = append(adj[a], [2]int{b, 1})  // 原始边a→b标记为1（需反转）adj[b] = append(adj[b], [2]int{a, 0})  // 反向边b→a标记为0（无需反转）}visited := make([]bool, n)queue := []int{0}visited[0] = truecount := 0for len(queue) > 0 {u := queue[0]queue = queue[1:]for _, vPair := range adj[u] {v, dir := vPair[0], vPair[1]if !visited[v] {visited[v] = truequeue = append(queue, v)count += dir // 方向标记为1的边需要反转}}}return count
}

二、算法分析

1. 核心思路

逆向树构建：以城市0为根构建逆向树，正确方向应为子节点→父节点
邻接表标记：每条边记录原始方向，正向边标记1（需反转），反向边标记0
广度优先遍历：从城市0出发逐层处理，累计方向标记为1的边数量

2. 关键步骤

邻接表初始化：为每个节点存储邻接关系和方向标记（15-19行）
BFS队列初始化：从根节点0开始遍历（22-23行）
方向判断逻辑：遇到标记为1的边需计入调整次数（30行）
防重复处理：使用visited数组避免重复访问（26行条件判断）

3. 复杂度

指标	值	说明
时间复杂度	O(n)	每个节点和边仅访问一次
空间复杂度	O(n)	邻接表存储n节点+n-1边信息

三、图解示例

在这里插入图片描述

四、边界条件与扩展

1. 特殊场景验证

单节点树：n=1时直接返回0（无需调整）
全逆向边：如[[1,0],[2,1],[3,2]]返回0
链式结构：0←1←2←3若原边全正向需反转3次

2. 扩展应用

动态网络更新：支持实时添加/删除边后快速计算
多目标优化：结合交通流量、排放等多因素决策
区域交通网络：扩展到公路、铁路多模式网络

五、多语言实现

from collections import dequedef minReorder(n: int, connections: list) -> int:graph = [[] for _ in range(n)]for a, b in connections:graph[a].append((b, 1))  # 正向边graph[b].append((a, 0))  # 反向边visited = [False]*nq = deque([0])visited[0] = Trueres = 0while q:u = q.popleft()for v, dir in graph[u]:if not visited[v]:visited[v] = Trueq.append(v)res += dirreturn res

class Solution {public int minReorder(int n, int[][] connections) {List<List<int[]>> adj = new ArrayList<>();for (int i = 0; i < n; i++) adj.add(new ArrayList<>());for (int[] conn : connections) {adj.get(conn[0]).add(new int[]{conn[1], 1});adj.get(conn[1]).add(new int[]{conn[0], 0});}boolean[] visited = new boolean[n];Queue<Integer> queue = new LinkedList<>();queue.offer(0);visited[0] = true;int count = 0;while (!queue.isEmpty()) {int u = queue.poll();for (int[] vPair : adj.get(u)) {int v = vPair[0], dir = vPair[1];if (!visited[v]) {visited[v] = true;queue.offer(v);count += dir;}}}return count;}
}

六、总结与优化

1. 核心创新点

逆向树遍历：通过反向构建树形结构确保连通性[^- 方向标记法：用0/1区分原始边方向实现快速判断
线性时间复杂度：BFS/DFS均实现O(n)高效计算

2. 工程优化方向

并行计算：子树分块处理加速大规模网络
内存压缩：用位运算替代二维数组存储方向
实时预测：结合交通流量预测动态调整

3. 算法扩展

多式联运网络：整合公路、铁路、航空多模式交通
故障容错机制：保证单边故障时的连通性
智能交通系统：与信号灯控制、路径规划联动优化

LeetCode算法题(Go语言实现)_45

题目 n 座城市，从 0 到 n-1 编号，其间共有 n-1 条路线。因此，要想在两座不同城市之间旅行只有唯一一条路线可供选择（路线网形成一颗树）。去年，交通运输部决定重新规划路线，以改变交通拥堵的状况…...

编程日记 2025/9/6 7:27:07

C++23 新特性：[[assume(expression)]] 属性

文章目录语法与基本用法作用与优化原理使用注意事项未满足假设时的行为使用场景示例代码总结 C23 引入了一个新的属性 [[assume(expression)]]，它为程序员提供了一种向编译器传递额外信息的机制，从而让编译器能够生成更高效的代码。语法与基本用法 …...

编程日记 2025/9/6 7:25:31

AI IDE 提示词

好的，这就将之前的分析内容整理成一篇适合发布在 CSDN 上的博客文章。告别代码生成混乱：AI IDE 提示词模式权威指南作者: (你的名字/昵称) 日期: 2025年4月14日前言随着人工智能技术的飞速发展，AI 助手（如 GitHub Copilot…...

编程日记 2025/8/17 20:02:04

整个 Binder 架构所涉及的总共有以下 5 个目录： 1. /framework/base/core/java/(Java) 2. /framework/base/core/jni/ (JNI) 3，/framework/native/libs/binder (Native) 4，/framework/native/cmds/servicemanager/ (Native) 5&#xff0c…...

编程日记 2025/9/6 7:27:04

三层交换机SVI功能（交换机虚拟接口）实现各个实训室电脑网络可互通，原本是独立局域网

三层交换机 SVI功能（交换机虚拟接口） 实现VLAN路由需求 ：各实训室使用独立局域网，即每个实训有自己的IP网段， 每个实训室只有内部互相访问。需求：为了加强各实训室学生的交流，学校要求我们…...

编程日记 2025/9/6 7:25:27

Spark-SQL核心编程：DataFrame、DataSet与RDD深度解析

在大数据处理领域，Spark-SQL是极为重要的工具。今天就来深入探讨Spark-SQL中DataFrame、DataSet和RDD这三个关键数据结构。 Spark-SQL的前身是Shark，它摆脱了对Hive的过度依赖，在数据兼容、性能优化和组件扩展上有显著提升。DataFrame是基于R…...

编程日记 2025/8/28 6:24:01

腾讯云COS直传，官方后端demo，GO语言转JAVA

腾讯云COS直传，官方后端demo，GO写的，我们台是JAVA所以转一下，已跑通。废话不多说，直接上代码： Controller类如下： import com.ruoyi.web.core.config.CosConfig; import org.springframework.beans.factory.annotation.Autowired; import org.springframework.http.Ht…...

编程日记 2025/8/17 18:59:55

c语言坦克对战（前言）

实现C语言中的“坦克大战”游戏逻辑，可以按照以下步骤进行： 游戏初始化定义游戏窗口：设置游戏窗口的大小和标题。加载资源：加载坦克、子弹、敌人等图像资源。初始化游戏状态：设置初始分数、生命值、坦克位置等。游…...

编程日记 2025/8/17 18:57:21

空间信息可视化——WebGIS前端实例（一）

技术栈：原生HTML 源代码：CUGLin/WebGIS: This is a project of Spatial information visualization 4 全国贫困县可视化系统 4.1 系统设计思想党的十九大报告明确指出,要“确保到2020年我国现行标准下农村贫困人口实现脱贫,贫困县全部摘帽,解决区域…...

编程日记 2025/9/6 7:27:05

JVM考古现场（十九）：量子封神·用鸿蒙编译器重铸天道法则

楔子：代码鸿蒙劫 "警告！警告！昆仑山服务器集群出现量子纠缠现象！"凌霄殿监控中心警报响彻云霄。全息投影中，Java线程在四维时空中编织出克莱因瓶拓扑结构，GC日志里闪烁着霍金辐射般的奇点事件。本…...

编程日记 2025/8/17 19:49:38

思维与算法共舞：AIGC语言模型的艺术与科学

云边有个稻草人-个人主页热门文章_云边有个稻草人的博客-本篇文章所属专栏~ 目录引言：AIGC与文本生成概述一、AIGC基础：语言模型的基本原理 1. 什么是语言模型？ 2. 预训练与微调二、AIGC的应用领域：文本生成的具体应用 …...

编程日记 2025/8/29 9:00:15

C++之多继承

在学校里有老师和学生，他们都是人，我么应该创建一个名为 Person 的基类和两个名为 Teacher 和Student 的子类，后两者是从前者继承来的有一部分学生还教课挣钱（助教），也就是同时存在着两个”是一个”关系&…...

编程日记 2025/8/17 18:58:22

AI模型的主要分类及其详细对比，涵盖任务类型、架构、数据需求、应用场景等维度，并附上典型代表模型

以下是 AI模型的主要分类及其详细对比，涵盖任务类型、架构、数据需求、应用场景等维度，并附上典型代表模型： 一、AI模型的主要分类 1. 按任务类型分类分类定义特点代表模型应用场景推理模型专注于逻辑推理、问题解决、因果关系分析的模型…...

编程日记 2025/8/29 3:11:09

TypeScript 快速入门

TypeScript 快速入门 1. 初识 TypeScript 1.1 TS 是什么？ 以 JavaScript 为基础构建的语言；一个 JavaScript 的超集；可以在任何支持 JavaScript 的平台执行；TypeScript 扩展了 JavaScript 并添加了类型；TS 不能被 J…...

编程日记 2025/8/17 18:58:23

第一章计算机网络和因特网

1.1 什么是因特网(Internet) 在博客这一系列文章中，我们使用一种特定的计算机网络，即公共因特网作为讨论计算机网络及其协议的主要载体。什么是因特网？可以用两种方式来回答这个问题：其一，我们能够通过因特网的具体构…...

编程日记 2025/8/17 18:57:14

【uni-app】axios 报错：Error: Adapter ‘http‘ is not available in the build

在 uni-app 中使用 axios 会报错：Error: Adapter ‘http‘ is not available in the build 解决方法：为 axios 添加 adapter 适配器。 import axios from axios; import settle from ../../node_modules/axios/lib/core/settle; import buildURL from …...

编程日记 2025/9/5 14:34:34

【路由交换方向IE认证】BGP选路原则之Weight属性

文章目录一、路由器BGP路由的处理过程控制平面和转发平面选路工具二、BGP的选路顺序选路的前提选路顺序三、Wight属性选路原则规则9与规则11的潜移默化使用Weight值进行选路直接更改Weight值进行选路配合使用route-map进行选路四、BGP邻居建立配置一、路由器BGP路由的处理…...

编程日记 2025/8/22 0:11:59

思科模拟器的单臂路由，交换机，路由器，路由器只要两个端口的话，连接三台电脑该怎么办，划分VLAN，dotlq协议

单臂路由 1. 需求：让三台电脑互通 2. 在二层交换机划分vlan，并加入； 3. 将连接二层交换机和路由器的端口f0/4改为trunk模式 4. 路由器：进入连接路由器的f0/0端口将端口开启 5. 进入每个vlan设dotlq协议并设网络IP&#xff08…...

编程日记 2025/9/2 20:16:08

计算机视觉与深度学习 | 基于Matlab的钢筋计数

===================================================== github：https://github.com/MichaelBeechan CSDN：https://blog.csdn.net/u011344545 ===================================================== 基于Matlab的钢筋计数 1、引言2、方法设计2.1 整体流程2.2 关键技术‌2…...

编程日记 2025/8/17 19:02:40

Pytorch深度学习框架60天进阶学习计划 - 第41天：生成对抗网络进阶（三）

Pytorch深度学习框架60天进阶学习计划 - 第41天：生成对抗网络进阶（三） 7. 实现条件WGAN-GP # 训练条件WGAN-GP def train_conditional_wgan_gp():# 用于记录损失d_losses []g_losses []# 用于记录生成样本的多样性（通过类别分…...

编程日记 2025/9/2 10:44:36

MySQL 用 limit 影响性能的优化方案

一.使用索引覆盖扫描如果我们只需要查询部分字段，而不是所有字段，我们可以尝试使用索引覆盖扫描，也就是让查询所需的所有字段都在索引中，这样就不需要再访问数据页，减少了随机 I/O 操作。例如，如果我们…...

编程日记 2025/8/17 20:19:13

粉末冶金齿轮学习笔记分享

有一段小段时间没有更新了，不知道小伙们有没有忘记我。最近总听到粉末冶金齿轮这个概念，花点时间来学习一下，总结一篇笔记分享给大家。废话不多说，直接开始： “粉末冶金”是一种制造工艺，包括在高压下压实…...

编程日记 2025/8/31 10:02:25

数据结构第五版【李春葆】

数据结构教程上机实验指导第5版（李春葆主编）.pdf 数据结构教程（第5版）（李春葆）.pdf 数据结构教程（第五版）课后习题参考答案（李春葆）.pdf 数据结构教…...

编程日记 2025/9/4 14:48:15

深入解析区块链技术：原理、应用与未来展望

1 区块链技术原理 1.1 基本概念区块链本质上是一个分布式账本，它由一系列按照时间顺序排列的数据块组成，每个数据块包含了一定时间内的交易信息。这些数据块通过密码学技术相互链接，形成一个不可篡改的链条。其核心特点包括去中心化、不可篡…...

编程日记 2025/8/28 14:32:57

SAX解析XML：Java程序员的“刑侦破案式“数据处理

各位XML侦探们！今天我们要化身代码界的福尔摩斯，学习用SAX解析XML——这种一边读文件一边破译线索的技术，就像在凶案现场逐帧查看监控录像，内存占用比你的咖啡杯还小！（DOM解析？那叫把整个监控室…...

编程日记 2025/9/5 21:00:40

Spring - 13 ( 11000 字 Spring 入门级教程 )

一： Spring AOP 备注：之前学习 Spring 学到 AOP 就去梳理之前学习的知识点了，后面因为各种原因导致 Spring AOP 的博客一直搁置。。。。。。下面开始正式的讲解。学习完 Spring 的统一功能后，我们就进入了 Spring AOP 的学习。…...

编程日记 2025/9/4 14:34:38

SQL 解析 with as dual sysdate level

目录 sql的运行顺序 with as EXTRACT 编辑 dual sysdate level 编辑编辑 Oracle中的日期存储核心部分拆解字符串并计算最小值关联子查询 NVL 函数 REGEXP_SUBSTR() sql的运行顺序 <select id"getTrendList" parameterType"java.util.H…...

编程日记 2025/9/4 19:00:14

苍穹外卖day03

店铺状态接口引入Redis，因为像存储店铺状态这种只有一个字段（没必要存储在数据库），且登录后台就要被访问的数据（加快查询速度，减少数据库压力） 使用步骤：导入相关maven依赖、配置…...

编程日记 2025/9/6 1:02:52

精品整理 | 云安全知识证书 (CCSK) v5 备考学习资源汇总

云安全知识证书 (CCSK) v5 备考学习资源，包含课件、视频、习题及CSA学习指南，共12章。 1.云计算的概念和架构 2.云治理 3.风险、审计与合规 4.组织管理 5.身份和访问管理 6.云安全监控 7.云基础设施和网络安全 8.云工作负载安全 9.云数据安全 10.云应用…...

编程日记 2025/8/27 13:25:28

编程思想——FP、OOP、FRP、AOP、IOC、DI、MVC、DTO、DAO

个人简介 👀个人主页： 前端杂货铺 🙋‍♂️学习方向： 主攻前端方向，正逐渐往全干发展 📃个人状态： 研发工程师，现效力于中国工业软件事业 🚀人生格言： 积跬步…...

编程日记 2025/9/2 18:57:19

使用SSH开通Linux服务器账号

文章目录 1. 通过SSH连接到服务器2. 创建账号3. 将用户设置为管理员（可选）4. 设置SSH登录权限（可选）（1）切换到该用户目录（2）创建.ssh目录并设置适当的权限 1. 通过SSH连接到服务器 …...

编程日记 2025/8/29 16:54:31

【C++】内存分配与释放、内存碎片、内存泄漏、栈溢出

C内存分配方式内存分配方式区别特性静态分配栈分配堆分配分配时机编译期函数调用时运行期（new） 释放方式自动释放函数结束自动释放手动delete释放内存区域静态存储区栈堆（自由存储区） 大小灵活性…...

编程日记 2025/9/5 21:45:42

论文：Generalized Category Discovery with Large Language Models in the Loop

论文下载地址：Generalized Category Discovery with Large Language Models in the Loop - ACL Anthology 1、研究背景尽管现代机器学习系统在许多任务上取得了优异的性能，绝大多数都遵循封闭世界的设置，假设训练和测试数据来自同一组预定义…...

编程日记 2025/9/4 7:56:37

k8s亲和力和非亲和力

在 Kubernetes 中，亲和力（Affinity）和非亲和力（Anti-Affinity）是用于控制 Pod 调度策略的机制，它们可以帮助优化资源利用率、提高应用性能和可用性。以下是亲和力和非亲和力的详细解释： 亲和力…...

编程日记 2025/9/2 16:40:06

Redis几个基本的全局指令

目录 1.set和get 2.keys 3.exists 4.del 5.expire 6.ttl 7.type 我们都知道Redis存的内容都是键值对，key是String，value有很多类型，像string（字符串），hash（哈希），…...

编程日记 2025/8/30 8:27:16

Flutter中如何判断一个计算任务是否耗时？

在 Flutter 里，判断一个计算任务是否耗时可从以下几个角度着手： 1. 任务复杂度分析数学运算复杂度：依据算法的时间复杂度来初步判断。例如，简单的加法、乘法运算时间复杂度为 O ( 1 ) O(1) O(1)，这类任务通常不耗时…...

编程日记 2025/9/6 3:16:57

LeetCode面试热题150中6-11题学习笔记（用Java语言描述）

Day 02 6、轮转数组需求：给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。方法一核心思想使用额外的数组来将每个元素放至正确的位置。用 n 表示数组的长度，遍历原数组，将原数组下标…...

编程日记 2025/9/5 20:41:30

驱动开发硬核特训 · Day 10 （理论上篇）：设备模型 ≈ 运行时的适配器机制

🔍 B站相应的视屏教程： 📌 内核：博文视频 - 总线驱动模型实战全解析敬请关注，记得标为原始粉丝。在 Linux 驱动开发中，设备模型（Device Model）是理解驱动架构的核心。而从软件工程…...

编程日记 2025/9/5 4:08:06

4.13日总结

javafx中实现发送qq邮箱验证码: 手动导入jar包方法： 第一步：开启QQ邮箱的 POP3/IMAP 或者 SMTP/IMAP 服务打开qq邮箱（电脑端），找到设置里的账号与安全的安全设置，往下滑就可以找到 POP3/IMAP 或者 SMTP…...

编程日记 2025/9/2 17:20:33

python 微博爬虫 01

起因， 目的: ✅下载单个视频，完成。✅ 获取某用户的视频列表，完成。剩下的就是， 根据视频列表，逐个下载视频，我没做，没意思。获取视频的评论，以后再说。关键点记录: 1. 对一个视…...

编程日记 2025/9/4 8:28:28

CST1017.基于Spring Boot+Vue共享单车管理系统

计算机/JAVA毕业设计【CST1017.基于Spring BootVue共享单车管理系统】【项目介绍】共享单车管理系统，基于 Spring Boot Vue 实现，功能丰富、界面精美【业务模块】系统共有四类用户，分别是：监管用户、运营用户、调度用户、普…...

编程日记 2025/9/5 8:57:29

小刚说C语言刷题——第23讲字符数组

前面，我们学习了一维数组和二维数组的概念。今天我们学习一种特殊的数组，字符数组。 1.字符数组的概念字符数组就是指元素类型为字符的数组。字符数组是用来存放字符序列或者字符串的。 2.字符数组的定义及语法 char ch[5]; 3.字符数组的初始化及赋…...

编程日记 2025/9/4 22:50:40

c++11--std::forwaord--完美转发

std::forword的作用完美转发的核心目的是保持参数的原始类型（包括const/volatile限定符和左值/右值性质）不变地传递给其他函数。为什么需要完美转发在没有完美转发之前，我们面临以下问题： 模板参数传递中的值类别丢失当参数…...

编程日记 2025/9/3 8:48:53

机器学习的一百个概念（12）学习率

前言本文隶属于专栏《机器学习的一百个概念》，该专栏为笔者原创，引用请注明来源，不足和错误之处请在评论区帮忙指出，谢谢！本专栏目录结构和参考文献请见[《机器学习的一百个概念》 ima 知识库知识库广场搜索：知识库创建人机器学习@Shockang机器学习数学基础@Shocka…...

编程日记 2025/9/4 22:27:52

java异常与泛型＜T＞

文章目录异常认识异常什么是异常？Java的异常体系异常的基本处理异常的作用？ 自定义异常编译时异常自定义运行时异常异常的处理方案泛型认识泛型泛型类泛型接口泛型方法、通配符、上下限泛型支持的类型包装类包装类具备的其他功能总结异常认识异常 …...

编程日记 2025/9/2 17:57:49

齐次坐标系统：什么是齐次坐标？为什么要引入齐次坐标？

齐次坐标系统：计算机图形学的基础在计算机图形学、计算机视觉、相机标定、三维建模等领域，齐次坐标是一个非常重要的数学工具。本文将介绍：齐次坐标的基本概念、数学原理、我们为什么要引入齐次坐标、及其在实际应用中的价值。文章目录齐…...

编程日记 2025/9/4 12:39:18

基于XGBoost的异烟酸生产收率预测：冠军解决方案解析

1. 引言在化工生产领域，准确预测产品收率对优化工艺流程、降低生产成本具有重要意义。本文以异烟酸生产为研究对象，通过机器学习方法构建预测模型，在包含10个生产步骤、42个工艺参数的数据集上实现高精度收率预测。该方案在工业竞赛中斩获冠军，本文将深度解析其技术实现细…...

编程日记 2025/9/3 15:25:20

vue3动态路由

要想实现vitevue-router实现动态路由我们需要用到 1. addRoute() 官方文档中addRoute的使用当我们添加一个主路由的时候 router.addRoute({ path: /permission, name: permission, component: () > import(xxxxx)}) 添加子路由也就是嵌套路由 router.addRoute(主路由的…...

编程日记 2025/9/1 12:47:14

Tkinter进度条与状态栏

在图形用户界面（GUI）应用中，进度条和状态栏是非常常见的控件，它们可以有效地向用户显示操作进度、状态信息或者任务完成情况。Tkinter提供了内置的控件和方法来实现进度条和状态栏的功能。在这一章中，我们将学习如何在Tkinter应用中使用进度条和状态栏来提升用户体验。 1…...

编程日记 2025/8/31 2:54:35

NModbus 库在 C# 中的使用

以下是关于 NModbus 库在 C# 中的使用方法的详细指南，涵盖从安装到实际通信的完整流程： 1. 安装 NModbus 库通过 NuGet 包管理器安装： Install-Package NModbus 或使用 .NET CLI： dotnet add package NModbus 2. 基础使用示例 2.1 创建 Modbus TCP 主站（Master） …...

编程日记 2025/8/29 20:53:53

题目