Leecode刷题C语言之统计好节点的数目
执行结果:通过
执行用时和内存消耗如下:

题目:统计好节点的数目
现有一棵 无向 树,树中包含 n 个节点,按从 0 到 n - 1 标记。树的根节点是节点 0 。给你一个长度为 n - 1 的二维整数数组 edges,其中 edges[i] = [ai, bi] 表示树中节点 ai 与节点 bi 之间存在一条边。
如果一个节点的所有子节点为根的子树包含的节点数相同,则认为该节点是一个 好节点。返回给定树中 好节点 的数量。子树 指的是一个节点以及它所有后代节点构成的一棵树。
解题思路:
- 定义节点结构:
- 使用
struct ListNode来表示树中的节点。每个节点包含一个整数值val和一个指向下一个节点的指针next。
- 使用
- 创建节点:
- 函数
create(int val)用于创建一个新的节点,并初始化其值为val,其next指针为NULL。该函数使用malloc动态分配内存,并检查内存分配是否成功。
- 函数
- 辅助数组和变量:
subtree_size[100010]:用于存储每个节点的子树大小(包括节点自身)。good_node_cnt:用于计数“好节点”的数量。
- 深度优先搜索(DFS):
- 函数
dfs(struct ListNode **adj, int cur, int pa)通过深度优先搜索遍历树。 adj是一个数组,其中adj[i]是一个链表的头节点,链表包含所有连接到节点i的节点。cur是当前访问的节点。pa是父节点的索引,用于避免在遍历子节点时回到父节点,形成环路。- 在遍历过程中,首先设置当前节点的子树大小为1(只包括节点自身)。
- 然后遍历当前节点的所有子节点(通过链表),对每个子节点递归调用
dfs。 - 累加每个子节点的子树大小到当前节点的子树大小。
- 跟踪第一个子节点的子树大小,并检查是否所有子节点的子树大小都相等。如果相等,则将当前节点标记为“好节点”。
- 函数
- 构建树的邻接表:
- 在
countGoodNodes函数中,首先计算节点的总数n(等于边数加1,因为无向树有n-1条边)。 - 初始化邻接表
adj,它是一个数组,其中每个元素是一个链表的头节点,链表包含连接到该节点的所有节点。 - 遍历边数组
edges,对于每条边(x, y),创建两个节点(如果尚未存在),并将它们添加到相应的邻接表中,形成双向连接。
- 在
- 计算好节点的数量:
- 调用
dfs函数,从根节点(节点0)开始遍历树。 - 在遍历完成后,
good_node_cnt变量将包含树中“好节点”的总数。
- 调用
- 返回结果:
- 函数
countGoodNodes返回“好节点”的总数。
- 函数
struct ListNode *create(int val) {struct ListNode *node = NULL;node = malloc(sizeof(*node));if (node == NULL) return NULL;node->val = val;node->next = NULL;return node;
}
int subtree_size[100010];
int good_node_cnt;
void dfs(struct ListNode **adj, int cur, int pa) {subtree_size[cur] = 1;int first_child_size = -1;bool is_good_node = true;for (struct ListNode *p = adj[cur]; p != NULL; p = p->next) {int child = p->val;if (child == pa) {continue;}dfs(adj, p->val, cur);subtree_size[cur] += subtree_size[child];if (first_child_size == -1) {first_child_size = subtree_size[child];} else {if (first_child_size != subtree_size[child]) {is_good_node = false;}}}if (is_good_node) {good_node_cnt++;}return ;
}
int countGoodNodes(int** edges, int edgesSize, int* edgesColSize) {int n = edgesSize + 1;good_node_cnt = 0;struct ListNode *adj[n];for (int i = 0; i < n; i++) {adj[i] = NULL;}for (int i = 0; i < edgesSize; i++) {int x = edges[i][0], y = edges[i][1];struct ListNode *xnode = create(x);xnode->next = adj[y];adj[y] = xnode;struct ListNode *ynode = create(y);ynode->next = adj[x];adj[x] = ynode;}dfs(adj, 0, -1);return good_node_cnt;
}
相关文章:
Leecode刷题C语言之统计好节点的数目
执行结果:通过 执行用时和内存消耗如下: 题目:统计好节点的数目 现有一棵 无向 树,树中包含 n 个节点,按从 0 到 n - 1 标记。树的根节点是节点 0 。给你一个长度为 n - 1 的二维整数数组 edges,其中 edges[i] [ai,…...
webpack5 + vue3 从零配置项目
前言 虽然在实际项目当中很少会从 0 到 1 配置一个项目,毕竟很多重复工作是没有必要的,脚手架将这些重复性的工作进行了整合,方便开发者使用。也正因如此,导致部分开发者过于依赖脚手架,却不清楚其内部的实现流程&…...
Queuing 表(buffer表)的优化实践 | OceanBase 性能优化实践
案例问题描述 该案例来自一个金融行业客户的问题:他们发现某个应用对一个数据量相对较小的表(仅包含数千条记录)访问时,频繁遇到性能下降的情况。为解决此问题,客户向我们求助进行分析。我们发现这张表有频繁的批量插…...
./mysqld: error while loading shared libraries: libaio.so.1: cannot open sha
mysql:5.6 使用离线方式安装:rpm -ivh --nodeps mysql* ,执行 systemctl start mysqld.service发现启动不了,通过vi /var/log/mysql.log看到如下关键字:libraries: libaio.so.1,之前也是按照网上帖子各种修改都没有解决…...
Qt主线程把数据发给子线程,主线程会阻塞吗
演示: #include <QCoreApplication> #include <QThread> #include <QObject> #include <QDebug>// 子线程类 class Worker : public QObject {Q_OBJECT public slots:void processData(int data) {qDebug() << "Processing dat…...
前后端、网关、协议方面补充
这里写目录标题 前后端接口文档简介前后端视角对于前端对于后端代码注册路由路由处理函数 关于httpGET/POST底层网络关于前端的获取 路由器网关路由器的IP简介公网IP(WAN IP)私网IP(LAN IP)无线网络IP(WIFI IP)查询路由器私网IP路由器公网IP LAN口与WIFI简介基本原理 手动配置电…...
如何在Mac上切换到JDK 17开发环境
在本文中,我将为您介绍如何在Mac上切换到JDK 17,包括下载和安装JDK 17、设置环境变量、在IntelliJ IDEA中配置项目、修改Maven编译配置,并最终使用mvn clean install重新编译项目。通过这个流程,您可以顺利地将开发环境升级到JDK …...
深入探索 TypeScript:从基础到高级特性
深入探索 TypeScript:从基础到高级特性 一、引言 在现代软件开发领域,TypeScript 已经成为了一种极具影响力的编程语言。它基于 JavaScript,并为其添加了强大的静态类型系统,使得代码在开发阶段就能进行更严格的类型检查&#x…...
Leetcode:118. 杨辉三角——Java数学法求解
题目——Leetcode:118. 杨辉三角 给定一个非负整数 numRows,生成「杨辉三角」的前 numRows 行。 在「杨辉三角」中,每个数是它左上方和右上方的数的和。 示例 1: 输入: numRows 5 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]示例 2: 输入: numRow…...
SHELL脚本(Linux)
声明 学习视频来自 B 站UP主泷羽sec,如涉及侵权马上删除文章。 笔记的只是方便各位师傅学习知识,以下网站只涉及学习内容,其他的都与本人无关,切莫逾越法律红线,否则后果自负。 ✍🏻作者简介:致…...
单元测试、集成测试、系统测试、验收测试、压力测试、性能测试、安全性测试、兼容性测试、回归测试(超详细的分类介绍及教学)
目录 1.单元测试 实现单元测试的方法: 注意事项: 2.集成测试 需注意事项: 实现集成测试的方法: 如何实现高效且可靠的集成测试: 3.系统测试 实现系统测试的方法: 须知注意事项: 4.验收测试 实现验…...
低代码集成多方API的简单实现
在现代软件开发中,集成多个API服务提供商已成为常见需求。然而,不同的API认证机制和数据格式使得集成过程变得复杂且耗时。为了应对这些挑战,本文将介绍一种低代码解决方案,通过配置化管理和简化的代码逻辑,帮助开发者…...
【测试框架篇】单元测试框架pytest(1):环境安装和配置
一、pytest简介 Pytest是Python的一种单元测试框架,与Python自带的unittest测试框架类似,但是比 unittest框架使用起来更简洁,效率更高。 二、pytest特点 Pytest是一个非常成熟的Python测试框架,主要特点有以下几点: 非常容易…...
Python数据分析NumPy和pandas(二十九、其他Python可视化工具)
与其他开源工具一样,在 Python 中创建图形有很多选项(太多了,无法一一列举)。自 2010 年以来,主要开发工作集中在创建用于在 Web 上发布交互式图形上。例如: Altair、Bokeh 和 Plotly 等工具,可…...
Unity中HDRP设置抗锯齿
一、以前抗锯齿的设置方式 【Edit】——>【Project Settings】——>【Quality】——>【Anti-aliasing】 二、HDRP项目中抗锯齿的设置方式 在Hierarchy中——>找到Camera对象——>在Inspector面板上——>【Camera组件】——>【Rendering】——>【Pos…...
Spring Boot实现文件上传与OSS集成:从基础到应用
目录 前言1. 文件上传的基础实现1.1 前端文件上传请求1.2 后端文件接收与保存 2. 集成第三方OSS服务2.1 准备工作2.2 编写OSS集成代码2.3 修改Controller实现文件上传至OSS 3. 文件上传的扩展:多文件上传与权限控制结语 前言 随着互联网应用的快速发展,…...
Python学习26天
集合 # 定义集合 num {1, 2, 3, 4, 5} print(f"num:{num}\nnum数据类型为:{type(num)}") # 求集合中元素个数 print(f"num中元素个数为:{len(num)}") # 增加集合中的元素 num.add(6) print(num) # {1,2,3,4,5,6} # 删除…...
linux startup.sh shutdown.sh (kkFileView)
linux启动脚本和关闭脚本startup.sh shutdown.sh (kkFileView) startup.sh DIR_HOME("/opt/openoffice.org3" "/opt/libreoffice" "/opt/libreoffice6.1" "/opt/libreoffice7.0" "/opt/libreoffice7.1&q…...
[MySQL]隐式类型转换
安全等号 <> 如果有参数为NULL,则除了相等比较运算符(),比较的结果为null。对于 nullnull,结果为true。 在select语句中,使用 时,结果不会包含值为 null 的记录,但如果使用安全等号 <> 来…...
面经总结1
文章目录 如何保证批量请求失败,只弹出一个toast1使用计数器:2使用标志变量: 如何减少项目里的if-else1使用多态2使用策略模式3使用字典映射4使用状态模式 babel-runtime 作用是啥如何实现 PDF 预览和下载1浏览器内置PDF阅读器2使用PDF.js库3…...
超短脉冲激光自聚焦效应
前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应,这是一种非线性光学现象,主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场,对材料产生非线性响应,可能…...
python打卡day49
知识点回顾: 通道注意力模块复习空间注意力模块CBAM的定义 作业:尝试对今天的模型检查参数数目,并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...
相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了: 这一篇我们开始讲: 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下: 一、场景操作步骤 操作步…...
23-Oracle 23 ai 区块链表(Blockchain Table)
小伙伴有没有在金融强合规的领域中遇见,必须要保持数据不可变,管理员都无法修改和留痕的要求。比如医疗的电子病历中,影像检查检验结果不可篡改行的,药品追溯过程中数据只可插入无法删除的特性需求;登录日志、修改日志…...
(二)原型模式
原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...
Android15默认授权浮窗权限
我们经常有那种需求,客户需要定制的apk集成在ROM中,并且默认授予其【显示在其他应用的上层】权限,也就是我们常说的浮窗权限,那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...
使用 SymPy 进行向量和矩阵的高级操作
在科学计算和工程领域,向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能,能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作,并通过具体…...
Java数值运算常见陷阱与规避方法
整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时,会出现小数部分被截断的情况。典型错误模式如下: void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...
【JVM面试篇】高频八股汇总——类加载和类加载器
目录 1. 讲一下类加载过程? 2. Java创建对象的过程? 3. 对象的生命周期? 4. 类加载器有哪些? 5. 双亲委派模型的作用(好处)? 6. 讲一下类的加载和双亲委派原则? 7. 双亲委派模…...
[大语言模型]在个人电脑上部署ollama 并进行管理,最后配置AI程序开发助手.
ollama官网: 下载 https://ollama.com/ 安装 查看可以使用的模型 https://ollama.com/search 例如 https://ollama.com/library/deepseek-r1/tags # deepseek-r1:7bollama pull deepseek-r1:7b改token数量为409622 16384 ollama命令说明 ollama serve #:…...
