【代码随想录day24】不同的二叉搜索树
题目
给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。
示例 1:

输入:n = 3 输出:5
示例 2:
输入:n = 1 输出:1
提示:
1 <= n <= 19
代码
定义dp[i]为由i个节点组成的二叉排序树有dp[i]种。
我们可以从节点数i为2开始遍历,每次遍历分别用j表示根节点左子树有j个节点,那对应右子树就有i-j-1个节点,那么左右子树分别能够组成的二叉排序树就是dp[j]和dp[i-j-1]种 ,j的取值范围是从0到i-1。题目要求的就是dp[j]*dp[i-j-1]。
这里当左右子树有为空的时候,我们应该把他当成1,不然dp[j]*dp[i-j-1]就是0了,但这种情况也是合理的,因此处理一下得到:dp[i]+=max(1,dp[j])*max(1,dp[i-j-1])。
class Solution:def numTrees(self, n: int) -> int:dp = [0 for _ in range(n+1)]dp[1]=1for i in range(2,n+1):for j in range(i):dp[i]+=max(1,dp[j])*max(1,dp[i-j-1])return dp[n]
相关文章:
【代码随想录day24】不同的二叉搜索树
题目 给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。 示例 1: 输入:n 3 输出:5示例 2: 输入:n 1 输出…...
数学建模--Subplot绘图的Python实现
目录 1.Subplot函数简介 2.Subplot绘图范例1:绘制规则子图 3.Subplot绘图范例2:绘制不规则子图 4.Subplot绘图范例3:gridspec辅助实战1 5.Subplot绘图范例4:gridspec辅助实战2 1.Subplot函数简介 """ 最近在数学建模种需要绘制多张子图,发现对于subplot函…...
JMeter(三十九):selenium怪异的UI自动化测试组合
文章目录 一、背景二、JMeter+selenium使用过程三、总结一、背景 题主多年前在某社区看到有人使用jmeter+selenium做UI自动化测试的时候,感觉很是诧异、怪异,为啥?众所周知在python/java+selenium+testng/pytest这样的组合框架下,为啥要选择jmeter这个东西[本身定位是接口测…...
c++ 移动构造方法为什么要加noexcept
背景: 最近看了候捷老师的c的教程, 他说移动构造方法要加noexcept, 在vector扩容的时候, 如果有移动构造方法没有加noexcept,是不会调用的. 个人感觉有些神奇, 这就去查下一探究竟. 过程: 测试代码如下: #include <iostream> #include <vector> struct A {A(){s…...
鸿鹄工程项目管理系统 Spring Cloud+Spring Boot+前后端分离构建工程项目管理系统
工程项目管理软件(工程项目管理系统)对建设工程项目管理组织建设、项目策划决策、规划设计、施工建设到竣工交付、总结评估、运维运营,全过程、全方位的对项目进行综合管理 工程项目各模块及其功能点清单 一、系统管理 1、数据字典&am…...
手把手教你搭建园林园艺小程序商城
现如今,随着互联网的快速发展,小程序成为了企业和个人展示产品和服务的新方式。在园林园艺行业,构建一个园林园艺小程序能够更好地推广和销售自己的产品和服务。那么,如何构建一个园林园艺小程序呢?下面我们来详细介绍…...
Java Iterator(迭代器)
Java迭代器(Iterator)是 Java 集合框架中的一种机制,是一种用于遍历集合(如列表、集合和映射等)的接口。 它提供了一种统一的方式来访问集合中的元素,而不需要了解底层集合的具体实现细节。 Iterator 是 …...
Logstash同步MySQL数据到ElasticSearch
当MySQL数据到一定的数量级,而且索引不能实现时,查询就会变得非常缓慢,所以使用ElasticSearch来查询数据。本篇博客介绍使用Logstash同步MySQL数据到ElasticSearch,再进行查询。 测试环境 Windows系统MySQL 5.7Logstash 7.0.1El…...
【C++】运算符重载的示例实现和应用
C运算符重载的格式: operator 运算符 比如要重载 ! 运算符 : operator ! 下面是一个例子: class DemoText{DemoText(string str, int num){m_text str; m_number num;}string m_text;int m_number; }这里来定义两个对象:…...
Kubernetes禁止调度
在Kubernetes中,您可以通过几种方式来禁止某个Pod调度到节点上。以下是一些方法: Node Selector:您可以使用Node Selector来限制Pod只能调度到带有特定标签的节点上。如果您希望完全禁止Pod调度到某些节点上,可以确保这些节点不拥…...
CocosCreator3.8研究笔记(七)CocosCreator 节点和组件的介绍
相信很多新手朋友,肯定会问,CocosCreator 中什么是节点?什么是组件? 一、什么是组件(Component)? Cocos Creator 3.8 的工作流程是以组件式开发为核心,即以组合而非继承的方式进行游…...
Ceph入门到精通-C++入门知识点
C中的双冒号(::)是作用域分解运算符(scope resolution operator)。 它主要有以下两种用法: 用于区分同名的不同成员,例如在不同类中声明了同名的成员函数或成员变量,可以使用A::B的方式来特指A类的B成员。当全局变量…...
Ansible之playbook详解和应用实例
目录 一、playbook简介 1.什么是playbook 2.playbook组成 二、应用实例 1.使用playbook安装启用httpd服务 2.使用playbook安装启用nginx服务 三、ansible-playbook其他用法 1.检查yaml文件的语法是否正确 2.检查tasks任务 3.检查指定的主机 4.指定从某个task开始运行…...
经验萃取方法
【经验萃取】 经验萃取不是简单的总结提炼归纳! 经验萃取需经过还原、复盘分析、萃取重构 一.经验萃取前三个准备 1.定主题: 萃取主题选择(阐述原因、确定级别、差距/问题是源头)->多维评分:普遍性、重要性、迫切…...
手写apply方法
<script>/** 手写apply方法 * */Function.prototype.myApply function (context, args) {console.log(this, sss)//fnconst key Symbol()context[key] thiscontext[key](...args)delete context[key]return context[key]}const obj {name: zs,age: 18}function fn …...
Jenkins实现基础CD操作
操作截图 在Jenkins里面设置通过标签进行构建 在Jenkins中进入项目,配置以下 将execute shell换到invoke top-level maven targets之前 在gitlab中配置标签 代码迭代新的版本 项目代码迭代 修改docker-compose.yml 提交新版本的代码 在Jenkins中追加新…...
开源软件合集(Docker)
Docker安装 1.安装命令:curl -fsSL https://get.docker.com | bash -s docker --mirror Aliyun2.启动:systemctl start docker3.停止:systemctl stop docker4.重启:systemctl restart docker5.开机启动:systemctl enab…...
Ceph入门到精通-生产日志级别设置
Ceph 子系统及其日志记录级别的信息。 了解 Ceph 子系统及其日志记录级别 Ceph 由多个子系统组成: 每个子系统都有其日志记录级别: 默认情况下存储在 /var/log/ceph/ 目录中的输出日志(日志级别)存储在内存缓存中的日志&#…...
16-MyCat
一 Mycat概述 1 什么是Mycat 什么是Mycat Mycat是数据库中间件,所谓数据库中间件是连接Java应用程序和数据库中间的软件。 为什么要用Mycat 遇到问题: Java与数据库的紧耦合高访问量高并发对数据库的压力读写请求数据不一致 2 Mycat与其他中间件区别 目…...
RKNPU2通用API和零拷贝API
RKNPU2通用API 通用API接口按照异构编程规范,需要将数据拷贝到NPU运行时的内存空间。 通用API部署流程 初始化上下文,需要先创建上下文对象和读取模型文件 rknn_context ctx; model load_model(model_path, &model_len); ret rknn_init(&ctx…...
Docker 离线安装指南
参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性,不同版本的Docker对内核版本有不同要求。例如,Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本,Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...
JavaSec-RCE
简介 RCE(Remote Code Execution),可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景:Groovy代码注入 Groovy是一种基于JVM的动态语言,语法简洁,支持闭包、动态类型和Java互操作性,…...
【入坑系列】TiDB 强制索引在不同库下不生效问题
文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...
【Linux】C语言执行shell指令
在C语言中执行Shell指令 在C语言中,有几种方法可以执行Shell指令: 1. 使用system()函数 这是最简单的方法,包含在stdlib.h头文件中: #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...
06 Deep learning神经网络编程基础 激活函数 --吴恩达
深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...
【开发技术】.Net使用FFmpeg视频特定帧上绘制内容
目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法,当前调用一个医疗行业的AI识别算法后返回…...
JVM虚拟机:内存结构、垃圾回收、性能优化
1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...
破解路内监管盲区:免布线低位视频桩重塑停车管理新标准
城市路内停车管理常因行道树遮挡、高位设备盲区等问题,导致车牌识别率低、逃费率高,传统模式在复杂路段束手无策。免布线低位视频桩凭借超低视角部署与智能算法,正成为破局关键。该设备安装于车位侧方0.5-0.7米高度,直接规避树枝遮…...
永磁同步电机无速度算法--基于卡尔曼滤波器的滑模观测器
一、原理介绍 传统滑模观测器采用如下结构: 传统SMO中LPF会带来相位延迟和幅值衰减,并且需要额外的相位补偿。 采用扩展卡尔曼滤波器代替常用低通滤波器(LPF),可以去除高次谐波,并且不用相位补偿就可以获得一个误差较小的转子位…...
数据结构:递归的种类(Types of Recursion)
目录 尾递归(Tail Recursion) 什么是 Loop(循环)? 复杂度分析 头递归(Head Recursion) 树形递归(Tree Recursion) 线性递归(Linear Recursion)…...
