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

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的一个主要思想是:对于任何一个满二叉树&#xff…...

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获取视频详情

话不多说&#xff0c;直接上代码&#xff1a; pom依赖&#xff1a; <!--视频多媒体工具包 包含 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

注释很详细&#xff0c;直接上代码 上一篇 新增内容 使用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字符串的全排列&#xff0c;返回起始位置 算法讲解 我们可以将这道题转化为寻找目标串的words字母的异位词&#xff0c;按照上一次讲解的【滑动窗口】Leetcode 找到字符串中所有字母异位词我们…...

golang channel实践代码及注意事项

在使用Go语言&#xff08;Golang&#xff09;的通道&#xff08;Channel&#xff09;时&#xff0c;有几个重要的注意点可以帮助开发者更安全、高效地使用它们进行并发编程。以下是一些关键的注意事项&#xff1a; 选择正确的通道类型&#xff1a;Go语言提供了两种类型的通道&…...

面试题:RabbitMQ 消息队列中间件

1. 确保消息不丢失 生产者确认机制 确保生产者的消息能到达队列&#xff0c;如果报错可以先记录到日志中&#xff0c;再去修复数据持久化功能 确保消息未消费前在队列中不会丢失&#xff0c;其中的交换机、队列、和消息都要做持久化消费者确认机制 由spring确认消息处理成功后…...

wpf中引用自定义字体

在WPF&#xff08;Windows Presentation Foundation&#xff09;中&#xff0c;FontFamily属性用于指定控件或文本元素使用的字体。它是一个非常基础且重要的属性&#xff0c;影响着用户界面的视觉呈现和可读性。以下是关于WPF中FontFamily属性的一些关键信息和使用方法&#x…...

高效准确!指甲剪盖片视觉检测技术解密

指甲剪的盖片是指指甲剪的一端&#xff0c;通常用来盖住另一端的刀刃部分。指甲剪盖片是指甲剪的重要部分&#xff0c;除了保护刀刃外&#xff0c;还起到美观和便捷的作用。正确使用和保养指甲剪盖片可以延长指甲剪的使用寿命。 本案是对指甲剪盖片最大尺寸长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中&#xff0c;事件是派生抽象QEvent类的对象&#xff0c;它表示应用程序内发生的事情&am…...

C++STL--排序算法

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

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

模型参数、模型存储精度、参数与显存

模型参数量衡量单位 M&#xff1a;百万&#xff08;Million&#xff09; B&#xff1a;十亿&#xff08;Billion&#xff09; 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的&#xff0c;但是一个参数所表示多少字节不一定&#xff0c;需要看这个参数以什么…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止

<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet&#xff1a; https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

ArcGIS Pro制作水平横向图例+多级标注

今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作&#xff1a;ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等&#xff08;ArcGIS出图图例8大技巧&#xff09;&#xff0c;那这次我们看看ArcGIS Pro如何更加快捷的操作。…...

动态 Web 开发技术入门篇

一、HTTP 协议核心 1.1 HTTP 基础 协议全称 &#xff1a;HyperText Transfer Protocol&#xff08;超文本传输协议&#xff09; 默认端口 &#xff1a;HTTP 使用 80 端口&#xff0c;HTTPS 使用 443 端口。 请求方法 &#xff1a; GET &#xff1a;用于获取资源&#xff0c;…...

【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)

前言&#xff1a; 双亲委派机制对于面试这块来说非常重要&#xff0c;在实际开发中也是经常遇见需要打破双亲委派的需求&#xff0c;今天我们一起来探索一下什么是双亲委派机制&#xff0c;在此之前我们先介绍一下类的加载器。 目录 ​编辑 前言&#xff1a; 类加载器 1. …...

pycharm 设置环境出错

pycharm 设置环境出错 pycharm 新建项目&#xff0c;设置虚拟环境&#xff0c;出错 pycharm 出错 Cannot open Local Failed to start [powershell.exe, -NoExit, -ExecutionPolicy, Bypass, -File, C:\Program Files\JetBrains\PyCharm 2024.1.3\plugins\terminal\shell-int…...

6️⃣Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙

Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙 一、前言:离区块链还有多远? 区块链听起来可能遥不可及,似乎是只有密码学专家和资深工程师才能涉足的领域。但事实上,构建一个区块链的核心并不复杂,尤其当你已经掌握了一门系统编程语言,比如 Go。 要真正理解区…...