Leetcode-894-所有可能的真二叉树-c++
题目详见https://leetcode.cn/problems/all-possible-full-binary-trees/
主搞动态规划,因为这玩意儿我还不是很懂
关于节点个数为奇数偶数的证明请见官方题解方法一中的如下内容:
这里DP的一个主要思想是:对于任何一个满二叉树,如果我们去掉根节点,那么剩下的部分就是两个更小的满二叉树。因此,我们可以通过将更小的满二叉树组合在一起来生成更大的满二叉树。
- 这就是为什么在代码中有两个嵌套的循环。
- 外层循环遍历所有的 i,代表我们想要生成的满二叉树的节点数量。
- 内层循环遍历所有的 j,代表左子树的节点数量。
- 因为满二叉树的节点总数必须是奇数(每个非叶节点都有两个子节点),所以 i 和 j 都是以 2 的步长增加的
- 对于每个 j,代码会遍历 dp[j] 和 dp[i-1-j] 中的所有可能的左子树和右子树。然后,它会创建一个新的满二叉树,其左子树和右子树分别是当前的左子树和右子树,然后将这个新的满二叉树添加到 dp[i] 中。
光看也不好理解,这里提供 n=7 的时候最后的dp数组的样子
{
此处偶数位为空, // dp[0]
{[0]}, // dp[1]
此处偶数位为空, // dp[2]
{[0,0,0]}, // dp[3], 这里不要数数组的长度,而要数节点(0)的个数
此处偶数位为空,
{[0,0,0,null,null,0,0], [0,0,0,0,0]}, // dp[5]
此处偶数位为空,
{[0,0,0,null,null,0,0,null,null,0,0], [0,0,0,null,null,0,0,0,0], [0,0,0,0,0,0,0], [0,0,0,0,0,null,null,null,null,0,0], [0,0,0,0,0,null,null,0,0]} // dp[7]
}
- 大家可以试试使用 d p [ a ] + 0 ( 这是个节点 ) + d p [ b ] dp[a] + 0(这是个节点) + dp[b] dp[a]+0(这是个节点)+dp[b] 来拼 d p [ a + b + 1 ] dp[a+b+1] dp[a+b+1]
- 比如使用 d p [ 1 ] + 0 ( 这是个节点 ) + d p [ 5 ] dp[1] + 0(这是个节点) + dp[5] dp[1]+0(这是个节点)+dp[5] 来拼 d p [ 7 ] dp[7] dp[7]
笔者也在新手学习期中,所写的内容主要与大家交流学习使用,如有发现任何问题敬请指正!
相关文章:

Leetcode-894-所有可能的真二叉树-c++
题目详见https://leetcode.cn/problems/all-possible-full-binary-trees/ 主搞动态规划,因为这玩意儿我还不是很懂 关于节点个数为奇数偶数的证明请见官方题解方法一中的如下内容: 这里DP的一个主要思想是:对于任何一个满二叉树ÿ…...

Django DRF视图
文章目录 一、DRF类视图介绍APIViewGenericAPIView类ViewSet类ModelViewSet类重写方法 二、Request与ResponseRequestResponse 参考 一、DRF类视图介绍 在DRF框架中提供了众多的通用视图基类与扩展类,以简化视图的编写。 • View:Django默认的视图基类&…...
SQLite全文搜索引擎:实现原理、应用实践和版本差异
文章目录 一、实现原理1.1 倒排索引1.2 虚拟表 二、应用在工程上的实施方法2.1 创建FTS虚拟表2.2 插入数据2.3 全文搜索2.4 关联普通表2.5 更新和删除数据2.6 优化FTS虚拟表2.7 小结 三、FTS3、FTS4和FTS5的区别3.1 FTS33.2 FTS43.3 FTS53.4 小结 四、更新SQLite的FTS版本的步骤…...
day17-二叉树part04
110.平衡二叉树 (优先掌握递归)后序遍历 左右中 class Solution {public boolean isBalanced(TreeNode root) {return getHeight(root) ! -1;}//递归三部曲 确定方法的参数与返回值private int getHeight(TreeNode root){//明确终止条件if(root null){r…...

书生浦语第一次课
模型的发展 从专业模型到通用模型 书生浦语大模型全链路开源体系 2023.06.07 -> InternLM千亿参数语言大模型发布 2023.07.06 -> InternLM千亿参数语言大模型全面升级,支持8K语境、26种语言。全面开源、免费商用:InternLM-7B、全链条开源工具…...

UE小:UE5.3无法创建C++工程
当您在使用Unreal Engine (UE) 构建项目时,如果遇到以下问题: Running C:/Program Files/Epic Games/UE\_5.3/Engine/Build/BatchFiles/Build.bat -projectfiles -project"C:/UEProject/Shp\_1/Shp\_1.uproject" -game -rocket -progress Usi…...

FFmpeg获取视频详情
话不多说,直接上代码: pom依赖: <!--视频多媒体工具包 包含 FFmpeg、OpenCV--><dependency><groupId>org.bytedeco</groupId><artifactId>javacv-platform</artifactId><version>1.5.3</versi…...
find: paths must precede expression
find: paths must precede expression 1. find: paths must precede expression2. 请在搜索字符串上添加单引号或者双引号References 1. find: paths must precede expression strongforeverstrong:~/ForeverStrong$ find /home/strong/ForeverStrong/image_results/ -name *.…...

RabbitMQ3.x之九_Docker中安装RabbitMQ
RabbitMQ3.x之_Docker中安装RabbitMQ 文章目录 RabbitMQ3.x之_Docker中安装RabbitMQ1. 官网2. 安装1 .拉取镜像2. 运行容器 3. 访问 1. 官网 rabbitmq - Official Image | Docker Hub 2. 安装 1 .拉取镜像 docker pull rabbitmq:3.13.0-management2. 运行容器 # latest Rabb…...

vue快速入门(四)v-html
注释很详细,直接上代码 上一篇 新增内容 使用v-html将文本以html的方式显示 源码 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, …...

第19次修改了可删除可持久保存的前端html备忘录:换了一个特别的倒计时时钟
第19次修改了可删除可持久保存的前端html备忘录:换了一个特别的倒计时时钟 <!DOCTYPE html> <html lang"zh"> <head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" content"IEedge"><met…...

C++ 2024-4-1 作业
#include <iostream> using namespace std;class A { public:int a;A(int a):a(a){cout<<"A的有参构造"<<endl;} }; class B:virtual public A { public:int b;B(int a,int b):A(a),b(b){cout<<"B的有参构造"<<endl;} }; cl…...

【滑动窗口】Leetcode 串联所有单词的子串
题目解析 30. 串联所有单词的子串 本题的意思就是在目标串s中寻找能够找到的words字符串的全排列,返回起始位置 算法讲解 我们可以将这道题转化为寻找目标串的words字母的异位词,按照上一次讲解的【滑动窗口】Leetcode 找到字符串中所有字母异位词我们…...
golang channel实践代码及注意事项
在使用Go语言(Golang)的通道(Channel)时,有几个重要的注意点可以帮助开发者更安全、高效地使用它们进行并发编程。以下是一些关键的注意事项: 选择正确的通道类型:Go语言提供了两种类型的通道&…...

面试题:RabbitMQ 消息队列中间件
1. 确保消息不丢失 生产者确认机制 确保生产者的消息能到达队列,如果报错可以先记录到日志中,再去修复数据持久化功能 确保消息未消费前在队列中不会丢失,其中的交换机、队列、和消息都要做持久化消费者确认机制 由spring确认消息处理成功后…...
wpf中引用自定义字体
在WPF(Windows Presentation Foundation)中,FontFamily属性用于指定控件或文本元素使用的字体。它是一个非常基础且重要的属性,影响着用户界面的视觉呈现和可读性。以下是关于WPF中FontFamily属性的一些关键信息和使用方法&#x…...

高效准确!指甲剪盖片视觉检测技术解密
指甲剪的盖片是指指甲剪的一端,通常用来盖住另一端的刀刃部分。指甲剪盖片是指甲剪的重要部分,除了保护刀刃外,还起到美观和便捷的作用。正确使用和保养指甲剪盖片可以延长指甲剪的使用寿命。 本案是对指甲剪盖片最大尺寸长75mm*宽10mm*高3mm…...
分布式IO模块PLC扩展模拟量模块
BL200是一款结构紧凑、体积小的分布式IO耦合器,支持ModbusTCP协议,采用嵌入式硬件,主频380Mhz,基于LinuxOS,采用独特的MAC层数据交换技术的双网口技术实现级联,中间设备宕机不影响后面设备的数据传输,可支持高达32个AI、DI、DO、热电阻、热电偶、RS485等种类的IO板,广泛应用于工…...
Qt事件系统
第三章Qt事件系统 文章目录 第三章Qt事件系统1.事件系统事件是如何传递的事件类型事件处理发送事件 2.事件传播机制事件接受和忽略事件分发事件过滤 3.事件和信号的区别 1.事件系统 在Qt中,事件是派生抽象QEvent类的对象,它表示应用程序内发生的事情&am…...

C++STL--排序算法
sort 使用快速排序,平均性能好O(nlogn),但最差情况可能很差O(n^2)。不稳定。 sort(v.begin(),v.end());//对v容器进行排序,默认升序 sort(v.begin(),v.end(),greater<int>());//降序排序对于支持随机访问的迭代器的容器, 都可以利用sort算法直接对其进行排序…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法
树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作,无需更改相机配置。但是,一…...

大型活动交通拥堵治理的视觉算法应用
大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动(如演唱会、马拉松赛事、高考中考等)期间,城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例,暖城商圈曾因观众集中离场导致周边…...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件
今天呢,博主的学习进度也是步入了Java Mybatis 框架,目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学,希望能对大家有所帮助,也特别欢迎大家指点不足之处,小生很乐意接受正确的建议&…...
基于Uniapp开发HarmonyOS 5.0旅游应用技术实践
一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架,支持"一次开发,多端部署",可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务,为旅游应用带来…...
大语言模型如何处理长文本?常用文本分割技术详解
为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...
Nginx server_name 配置说明
Nginx 是一个高性能的反向代理和负载均衡服务器,其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机(Virtual Host)。 1. 简介 Nginx 使用 server_name 指令来确定…...
什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南
文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果: 一刀斩断视频片头广告
一刀流:用一个简单脚本,秒杀视频片头广告,还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农,平时写代码之余看看电影、补补片,是再正常不过的事。 电影嘛,要沉浸,…...

【网络安全】开源系统getshell漏洞挖掘
审计过程: 在入口文件admin/index.php中: 用户可以通过m,c,a等参数控制加载的文件和方法,在app/system/entrance.php中存在重点代码: 当M_TYPE system并且M_MODULE include时,会设置常量PATH_OWN_FILE为PATH_APP.M_T…...

【LeetCode】算法详解#6 ---除自身以外数组的乘积
1.题目介绍 给定一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O…...