c++ 图论2 深度优先算法和广度优先算法
修改一下深度优先算法和广度优先算法,标出每一个节点相对于遍历起始位置的层级,遍历起始起点为第一层,和第一层相连的节点为第二层,以此类推
定义一个新的结构
struct NodeWithLevel {TreeNode* node;int level;NodeWithLevel(TreeNode* n, int l) : node(n), level(l) {}
};
深度优先搜索(DFS)
class Solution {
public:vector<NodeWithLevel> dfsWithLevel(TreeNode* root) {vector<NodeWithLevel> result;dfsHelper(root, 1, result);return result;}private:void dfsHelper(TreeNode* node, int level, vector<NodeWithLevel>& result) {if (node == nullptr) {return;}// 将当前节点及其层级添加到结果中result.push_back(NodeWithLevel(node, level));// 递归处理左子树,层级加1dfsHelper(node->left, level + 1, result);// 递归处理右子树,层级加1dfsHelper(node->right, level + 1, result);}
};
DFS算法的工作原理:
- 我们使用一个辅助函数
dfsHelper,它接受当前节点、当前层级和结果vector作为参数。 - 如果当前节点为空,我们直接返回。
- 我们将当前节点和其层级添加到结果中。
- 然后我们递归地处理左子树和右子树,每次递归时层级加1。
广度优先搜索(BFS):
class Solution {
public:vector<NodeWithLevel> bfsWithLevel(TreeNode* root) {vector<NodeWithLevel> result;if (root == nullptr) {return result;}queue<NodeWithLevel> q;q.push(NodeWithLevel(root, 1));while (!q.empty()) {NodeWithLevel current = q.front();q.pop();// 将当前节点及其层级添加到结果中result.push_back(current);// 如果左子节点存在,将其加入队列,层级加1if (current.node->left) {q.push(NodeWithLevel(current.node->left, current.level + 1));}// 如果右子节点存在,将其加入队列,层级加1if (current.node->right) {q.push(NodeWithLevel(current.node->right, current.level + 1));}}return result;}
};
这个BFS算法的工作原理:
- 我们创建一个队列来存储
NodeWithLevel对象。 - 我们从根节点开始,将其作为第一层加入队列。
- 当队列不为空时,我们取出队首元素,将其添加到结果中。
- 然后我们检查当前节点的左右子节点,如果存在,就将它们加入队列,层级为当前节点的层级加1。
- 重复这个过程直到队列为空。
这两种算法都会返回一个 vector<NodeWithLevel>,其中包含了树中所有节点及其对应的层级。DFS 通常会以前序遍历的顺序返回节点,而 BFS 会按照层序遍历的顺序返回节点。
相关文章:
c++ 图论2 深度优先算法和广度优先算法
修改一下深度优先算法和广度优先算法,标出每一个节点相对于遍历起始位置的层级,遍历起始起点为第一层,和第一层相连的节点为第二层,以此类推 定义一个新的结构 struct NodeWithLevel {TreeNode* node;int level;NodeWithLevel(T…...
【Qt】初识QtQt Creator
一.简述Qt 1.什么是Qt Qt 是⼀个 跨平台的 C 图形⽤⼾界⾯应⽤程序框架 。它为应⽤程序开发者提供了建⽴艺术级图形界⾯所需的所有功能。它是完全⾯向对象的,很容易扩展。Qt 为开发者提供了⼀种基于组件的开发模式,开发者可以通过简单的拖拽和组合来实现…...
Android 11.0 修改系统显示大小导航栏消失
Android 11.0 修改系统显示大小导航栏消失 1.显示大小设置为大时,导航栏图标不显示。 设置为大,较大,最大时,导航栏图标不显示。 2.开始怀疑是导航栏被隐藏了,各种折腾无效。 3.发现: frameworks/base/pa…...
RocketMQ源码学习笔记:Producer启动流程
这是本人学习的总结,主要学习资料如下 马士兵教育rocketMq官方文档 目录 1、Overview1.1、创建MQClientInstance1.1.1、检查1.1.1、MQClientInstance的ID 1.2、MQClientInstance.start() 1、Overview 这是发送信息的代码样例, DefaultMQProducer produ…...
Node.js 和浏览器环境中都使用 WebSocket
使用WebSocket为什么不适配双端 浏览器环境本身就支持 WebSocket,直接使用 JavaScript 内置的 WebSocket 对象来建立连接。 Node中本身并没有内置 WebSocket 协议的支持,所以需要使用第三方库 ws来实现 WebSocket 功能。 一. 使用跨平台 WebSocket 库 …...
css美化滚动条样式
效果展示 实现 滚动条宽,高度 /* 整体滚动条 */ ::-webkit-scrollbar {width: 10px; }/* 滚动条轨道 */ ::-webkit-scrollbar-track {background-color: #ffffff;border-radius: 6px; }/* 滚动条滑块 */ ::-webkit-scrollbar-thumb {background-color: #888;borde…...
由浅入深,走进深度学习(补充篇:转置卷积和FCN)
本期内容是针对神经网络层结构的一个补充,主要内容是:转置卷积和全连接卷积网络 相关内容: 由浅入深,走进深度学习(2)_卷积层-CSDN博客 由浅入深,走进深度学习(补充篇:…...
Linux基础篇——目录结构
基本介绍 Linux的文件系统是采用级层式的树状目录结构,在此结构中的最上层是根目录"/",然后在根目录下再创建其他的目录 在Linux中,有一句经典的话:在Linux世界里,一切皆文件 Linux中根目录下的目录 具体的…...
星际编码:Swifter.Json,.NET宇宙中的数据处理新星
概述 在数字化的星辰大海中,数据是宇宙的通用语言。在.NET这一广袤的星系中,JSON作为信息交换的媒介,扮演着至关重要的角色。今天,我们要探索的是一颗新星——Swifter.Json,一个功能全面且性能卓越的JSON序列化和反序列…...
python 压缩数据
requests 是 Python 中一个非常流行的 HTTP 库,用于发送各种 HTTP 请求。下面是一个使用 requests 库发送简单 GET 请求和 POST 请求的示例: 首先,确保你已经安装了 requests 库。如果还没有安装,可以使用 pip 进行安装ÿ…...
nacos在k8s上的集群安装实践
目录 概述实践nfs安装使用 k8s持久化nacos安装创建角色部署数据库执行数据库初始化语句部署nacos ingress效果展示问题修复 结束 概述 本文主要对 nacos 在k8s上的集群安装 进行说明与实践。主要版本信息,k8s: 1.27.x,nacos: 2.0.3。运行环境为 centos 7…...
数据结构—判断题
1.数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的存储结构。 答案:错误 2.(neuDS)在顺序表中逻辑上相邻的元素,其对应的物理位置也是相邻的。 答案:正确 3.若一个栈的输入序列为{1, 2, 3, 4, 5},则不…...
树莓派挂载的移动硬盘badblocks坏道屏蔽,以这个为准
!!!use 这里要设置块大小和磁盘相同 badblocks -b 4096 -s -c 512 -v -o /a/2/bads4.txt /dev/sda5 检测完重新检测跳过之前的记录 badblocks -i /a/2/bads4.txt -b 4096 -s -c 512 -v -o /a/2/bads5.txt /dev/sda5 可以查看磁盘具体block总数和大小 sudo dumpe2fs /dev/sda5 …...
Unity开箱即用的UGUI面板的拖拽移动功能
文章目录 👉一、背景👉二、效果图👉三、原理👉四、核心代码👉五,总结 👉一、背景 之前做PC项目时常常有面板拖拽移动的需求,今天总结封装一下,做成一个随时随地可复用的…...
春秋云境:CVE-2022-25411[漏洞复现]
根据题目提示和CNNVD优先寻找后台管理地址 靶机启动后,使用AWVS进行扫描查看网站结构 在这里可以看到后台管理的登录地址:/admin/,根据题目提示可知是弱口令 尝试admin、123456、admin666、admin123、admin888...等等常见弱口令 正确的账户…...
java基础知识点全集
JAVA的所有知识点 一、基础的数组、数据类型、输入输出二、类与对象1. 三大特征(1) 封装(2)继承(3)多态 2. 类的实例化(1) 类通过NEW来创建(2) 类的继承&…...
如何完成域名解析验证
一:什么是DNS解析: DNS解析是互联网上将人类可读的域名(如www.example.com)转换为计算机可识别的IP地址(如192.0.2.1)的过程,大致遵循以下步骤: 查询本地缓存:当用户尝…...
2024年6月个人工作生活总结
title: 2024年6月个人工作生活总结 urlname: code-for-2024-06 tags: 代码积累知识总结 categories:我的程序代码 date: 2024-06-30 00:00:00 photos:gallery/tech/c2.jpg 本文为 2024年6月工作生活总结。 研发编码 编码和注释 因某些需要,重拾了2019年的工程代码…...
Json与Java类
简介 JSON(JavaScript Object Notation)是一种轻量级的数据交换格式,易于人阅读和编写,同时也易于机器解析和生成。JSON数据由键值对构成,并以易于阅读的文本形式展现,支持数组、对象、字符串、数字、布尔值…...
动手学深度学习(Pytorch版)代码实践 -计算机视觉-39实战Kaggle比赛:狗的品种识别(ImageNet Dogs)
39实战Kaggle比赛:狗的品种识别(ImageNet Dogs) 比赛链接:Dog Breed Identification | Kaggle 1.导入包 import torch from torch import nn import collections import math import os import shutil import torchvision from…...
Linux 文件类型,目录与路径,文件与目录管理
文件类型 后面的字符表示文件类型标志 普通文件:-(纯文本文件,二进制文件,数据格式文件) 如文本文件、图片、程序文件等。 目录文件:d(directory) 用来存放其他文件或子目录。 设备…...
Zustand 状态管理库:极简而强大的解决方案
Zustand 是一个轻量级、快速和可扩展的状态管理库,特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...
相机从app启动流程
一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...
3-11单元格区域边界定位(End属性)学习笔记
返回一个Range 对象,只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意:它移动的位置必须是相连的有内容的单元格…...
Docker 本地安装 mysql 数据库
Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker ;并安装。 基础操作不再赘述。 打开 macOS 终端,开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...
纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join
纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...
【JVM】Java虚拟机(二)——垃圾回收
目录 一、如何判断对象可以回收 (一)引用计数法 (二)可达性分析算法 二、垃圾回收算法 (一)标记清除 (二)标记整理 (三)复制 (四ÿ…...
MySQL 主从同步异常处理
阅读原文:https://www.xiaozaoshu.top/articles/mysql-m-s-update-pk MySQL 做双主,遇到的这个错误: Could not execute Update_rows event on table ... Error_code: 1032是 MySQL 主从复制时的经典错误之一,通常表示ÿ…...
HybridVLA——让单一LLM同时具备扩散和自回归动作预测能力:训练时既扩散也回归,但推理时则扩散
前言 如上一篇文章《dexcap升级版之DexWild》中的前言部分所说,在叠衣服的过程中,我会带着团队对比各种模型、方法、策略,毕竟针对各个场景始终寻找更优的解决方案,是我个人和我司「七月在线」的职责之一 且个人认为,…...
Visual Studio Code 扩展
Visual Studio Code 扩展 change-case 大小写转换EmmyLua for VSCode 调试插件Bookmarks 书签 change-case 大小写转换 https://marketplace.visualstudio.com/items?itemNamewmaurer.change-case 选中单词后,命令 changeCase.commands 可预览转换效果 EmmyLua…...
