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

【代码随想录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 &#xff0c;求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种&#xff1f;返回满足题意的二叉搜索树的种数。 示例 1&#xff1a; 输入&#xff1a;n 3 输出&#xff1a;5示例 2&#xff1a; 输入&#xff1a;n 1 输出&#xf…...

数学建模--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+前后端分离构建工程项目管理系统

工程项目管理软件&#xff08;工程项目管理系统&#xff09;对建设工程项目管理组织建设、项目策划决策、规划设计、施工建设到竣工交付、总结评估、运维运营&#xff0c;全过程、全方位的对项目进行综合管理 工程项目各模块及其功能点清单 一、系统管理 1、数据字典&am…...

手把手教你搭建园林园艺小程序商城

现如今&#xff0c;随着互联网的快速发展&#xff0c;小程序成为了企业和个人展示产品和服务的新方式。在园林园艺行业&#xff0c;构建一个园林园艺小程序能够更好地推广和销售自己的产品和服务。那么&#xff0c;如何构建一个园林园艺小程序呢&#xff1f;下面我们来详细介绍…...

Java Iterator(迭代器)

Java迭代器&#xff08;Iterator&#xff09;是 Java 集合框架中的一种机制&#xff0c;是一种用于遍历集合&#xff08;如列表、集合和映射等&#xff09;的接口。 它提供了一种统一的方式来访问集合中的元素&#xff0c;而不需要了解底层集合的具体实现细节。 Iterator 是 …...

Logstash同步MySQL数据到ElasticSearch

当MySQL数据到一定的数量级&#xff0c;而且索引不能实现时&#xff0c;查询就会变得非常缓慢&#xff0c;所以使用ElasticSearch来查询数据。本篇博客介绍使用Logstash同步MySQL数据到ElasticSearch&#xff0c;再进行查询。 测试环境 Windows系统MySQL 5.7Logstash 7.0.1El…...

【C++】运算符重载的示例实现和应用

C运算符重载的格式&#xff1a; operator 运算符 比如要重载 ! 运算符 &#xff1a; operator ! 下面是一个例子&#xff1a; class DemoText{DemoText(string str, int num){m_text str; m_number num;}string m_text;int m_number; }这里来定义两个对象&#xff1a;…...

Kubernetes禁止调度

在Kubernetes中&#xff0c;您可以通过几种方式来禁止某个Pod调度到节点上。以下是一些方法&#xff1a; Node Selector&#xff1a;您可以使用Node Selector来限制Pod只能调度到带有特定标签的节点上。如果您希望完全禁止Pod调度到某些节点上&#xff0c;可以确保这些节点不拥…...

CocosCreator3.8研究笔记(七)CocosCreator 节点和组件的介绍

相信很多新手朋友&#xff0c;肯定会问&#xff0c;CocosCreator 中什么是节点&#xff1f;什么是组件&#xff1f; 一、什么是组件&#xff08;Component&#xff09;&#xff1f; Cocos Creator 3.8 的工作流程是以组件式开发为核心&#xff0c;即以组合而非继承的方式进行游…...

Ceph入门到精通-C++入门知识点

C中的双冒号(::)是作用域分解运算符&#xff08;scope resolution operator&#xff09;。 它主要有以下两种用法&#xff1a; 用于区分同名的不同成员&#xff0c;例如在不同类中声明了同名的成员函数或成员变量&#xff0c;可以使用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开始运行…...

经验萃取方法

【经验萃取】 经验萃取不是简单的总结提炼归纳&#xff01; 经验萃取需经过还原、复盘分析、萃取重构 一.经验萃取前三个准备 1.定主题&#xff1a; 萃取主题选择&#xff08;阐述原因、确定级别、差距/问题是源头&#xff09;->多维评分&#xff1a;普遍性、重要性、迫切…...

手写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中进入项目&#xff0c;配置以下 将execute shell换到invoke top-level maven targets之前 在gitlab中配置标签 代码迭代新的版本 项目代码迭代 修改docker-compose.yml 提交新版本的代码 在Jenkins中追加新…...

开源软件合集(Docker)

Docker安装 1.安装命令&#xff1a;curl -fsSL https://get.docker.com | bash -s docker --mirror Aliyun2.启动&#xff1a;systemctl start docker3.停止&#xff1a;systemctl stop docker4.重启&#xff1a;systemctl restart docker5.开机启动&#xff1a;systemctl enab…...

Ceph入门到精通-生产日志级别设置

Ceph 子系统及其日志记录级别的信息。 了解 Ceph 子系统及其日志记录级别 Ceph 由多个子系统组成&#xff1a; 每个子系统都有其日志记录级别&#xff1a; 默认情况下存储在 /var/log/ceph/ 目录中的输出日志&#xff08;日志级别&#xff09;存储在内存缓存中的日志&#…...

16-MyCat

一 Mycat概述 1 什么是Mycat 什么是Mycat Mycat是数据库中间件&#xff0c;所谓数据库中间件是连接Java应用程序和数据库中间的软件。 为什么要用Mycat 遇到问题&#xff1a; Java与数据库的紧耦合高访问量高并发对数据库的压力读写请求数据不一致 2 Mycat与其他中间件区别 目…...

RKNPU2通用API和零拷贝API

RKNPU2通用API 通用API接口按照异构编程规范&#xff0c;需要将数据拷贝到NPU运行时的内存空间。 通用API部署流程 初始化上下文&#xff0c;需要先创建上下文对象和读取模型文件 rknn_context ctx; model load_model(model_path, &model_len); ret rknn_init(&ctx…...

挑战杯推荐项目

“人工智能”创意赛 - 智能艺术创作助手&#xff1a;借助大模型技术&#xff0c;开发能根据用户输入的主题、风格等要求&#xff0c;生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用&#xff0c;帮助艺术家和创意爱好者激发创意、提高创作效率。 ​ - 个性化梦境…...

基于大模型的 UI 自动化系统

基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...

基于Flask实现的医疗保险欺诈识别监测模型

基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施&#xff0c;由雇主和个人按一定比例缴纳保险费&#xff0c;建立社会医疗保险基金&#xff0c;支付雇员医疗费用的一种医疗保险制度&#xff0c; 它是促进社会文明和进步的…...

Qt Widget类解析与代码注释

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码&#xff0c;写上注释 当然可以&#xff01;这段代码是 Qt …...

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面

代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http…...

如何在网页里填写 PDF 表格?

有时候&#xff0c;你可能希望用户能在你的网站上填写 PDF 表单。然而&#xff0c;这件事并不简单&#xff0c;因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件&#xff0c;但原生并不支持编辑或填写它们。更糟的是&#xff0c;如果你想收集表单数据&#xff…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题

在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件&#xff0c;这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下&#xff0c;实现高效测试与快速迭代&#xff1f;这一命题正考验着…...

基于TurtleBot3在Gazebo地图实现机器人远程控制

1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...

LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》

这段 Python 代码是一个完整的 知识库数据库操作模块&#xff0c;用于对本地知识库系统中的知识库进行增删改查&#xff08;CRUD&#xff09;操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 &#x1f4d8; 一、整体功能概述 该模块…...

Linux中《基础IO》详细介绍

目录 理解"文件"狭义理解广义理解文件操作的归类认知系统角度文件类别 回顾C文件接口打开文件写文件读文件稍作修改&#xff0c;实现简单cat命令 输出信息到显示器&#xff0c;你有哪些方法stdin & stdout & stderr打开文件的方式 系统⽂件I/O⼀种传递标志位…...