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

leetcode0096. 不同的二叉搜索树-medium

news 来源：原创 2025/7/18 4:42:30

1 题目：不同的二叉搜索树

官方标定难度：中

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

示例 1：

在这里插入图片描述

输入：n = 3
输出：5

示例 2：

输入：n = 1
输出：1

提示：

1 <= n <= 19

2 solution

根据根节点进行分类，n 个节点的二叉搜索树有 d p n dp_n dpn​ 个，则有

d p n = ∑ i = 0 n − 1 d p i ∗ d p n − i − 1 dp_n = \sum_{i = 0} ^ {n -1} dp_i * dp_{n- i - 1} dpn​=i=0∑n−1​dpi​∗dpn−i−1​

所以直接递推即可

代码

class Solution {
public:
int numTrees(int n) {int dp[n + 1];dp[0] = dp[1] = 1;for(int i = 2; i <= n; i++){dp[i] = 0;for(int l = 0; l < i; l++){dp[i] += dp[l] * dp[i - l - 1];}}return dp[n];
}
};

结果

加粗样式

3 进阶

这其实就是卡特兰数，有更简单的地推公式。

d p n = d p n − 1 ⋅ 4 ∗ n − 2 i + 1 dp_n = dp_{n-1} \cdot \frac {4 * n - 2} {i + 1} dpn​=dpn−1​⋅i+14∗n−2​

代码

class Solution {/**  C(n) = c(2n, n) - c(2n, n-1) = n+2...2n / n!*  C(n) / C(n - 1) = (4n-2) / (n+1)*  C(1) = 1*/
public:int numTrees(int n) {int s = 1; //for (int i = 2; i <= n; i++) {s = 1ll * s * (4 * i - 2) / (i + 1);}return s;}
};

结果

在这里插入图片描述

相关文章：

leetcode0096. 不同的二叉搜索树-medium

1 题目&#xff1a;不同的二叉搜索树 官方标定难度&#xff1a;中 给你一个整数 n &#xff0c;求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种&#xff1f;返回满足题意的二叉搜索树的种数。 示例 1&#xff1a; 输入&#xff1a;n 3 输出&#xf…...

编程日记 2025/7/18 4:42:30

【科研绘图系列】R语言绘制世界地图（map plot）

禁止商业或二改转载，仅供自学使用，侵权必究，如需截取部分内容请后台联系作者! 文章目录 介绍加载R包数据下载导入数据数据预处理画图输出图片系统信息介绍 【科研绘图系列】R语言绘制世界地图（map plot） 加载R包 library(ggmap) library(RColorBrewer) library(pals) …...

编程日记 2025/7/18 4:38:38

【原创】风云扫描王[特殊字符]OCR识别翻译！证件照

&#x1f4e3;文字识别&#xff0c;文字提取&#xff0c;扫描翻译&#xff0c;证件扫描&#xff0c;表格识别&#xff0c;PDF加水印等一体的扫描应用。扫描任何东西&#xff0c;包括文件、纸质笔记、收据和书籍&#xff0c;把它们扫描成清晰的PDF文件和图像。使用OCR技术将图像…...

编程日记 2025/7/5 12:05:49

Fabrice Bellard（个人网站：‌bellard.org‌）介绍

Fabrice Bellard 是法国人&#xff0c;国际知名程序员。 Fabrice Bellard&#xff08;个人网站&#xff1a;‌bellard.org‌&#xff09;是计算机领域最具影响力的程序员之一&#xff0c;其贡献跨越多个技术领域并持续推动开源生态发展。以下是其关键成就与技术贡献的梳理&…...

编程日记 2025/6/29 6:27:41

Linux电源管理(5)_Hibernate和Sleep功能介绍

原文&#xff1a;Linux电源管理(5)_Hibernate和Sleep功能介绍 1. 前言 Hibernate和Sleep两个功能是Linux PM的核心功能&#xff0c;它们的目的是类似的&#xff1a;暂停使用——>保存上下文——>关闭系统以节电>恢复系统——>恢复上下文——>继续使用。 本文…...

编程日记 2025/7/18 4:37:14

【C/C++】Linux的futex锁

文章目录 Linux Futex1. 概述2. 核心设计思想3. Futex 系统调用接口4. 核心操作4.1 阻塞等待 (FUTEX_WAIT)4.2 唤醒线程 (FUTEX_WAKE)4.3 进阶操作 5. Futex 的使用场景5.1 实现用户态互斥锁 (Mutex)5.2 实现条件变量 (Condition Variable) 6. Futex 的优缺点7. Futex 与传统同…...

编程日记 2025/7/18 4:42:29

ChatGPT：重塑人工智能交互范式的破晓之作

2022年11月30日&#xff0c;总部位于旧金山的研究公司OpenAI正式发布了ChatGPT——一款以病毒式传播速度席卷全球的AI聊天机器人。它不仅能像人类一样生成内容、回答问题和解决问题&#xff0c;更在推出后的两个月内吸引了超过1亿月活跃用户&#xff0c;刷新了消费级技术应用的…...

编程日记 2025/6/29 7:14:22

java面向对象编程【高级篇】之特殊类

目录 &#x1f680;前言&#x1f31f;final关键字&#x1f4af;常量 &#x1f99c;单例类&#x1f4af;饿汉式单例类&#x1f4af;懒汉式单例类 ✍️枚举类&#x1f40d;抽象类&#x1f4af;应用场景&#x1f4af;模版方法设计模式 ⚙️接口&#x1f4af;实现类&#x1f4af;接…...

编程日记 2025/6/29 7:55:59

JVM 一文详解

目录 JVM 简介 JVM 中的内存区域划分 1. 堆&#xff08;一个进程只有一份 ------ 线程共享&#xff09; 2. 栈&#xff08;一个进程可以有 N 份 ------ 线程私有&#xff09; Java 虚拟机栈&#xff1a; 本机方法栈&#xff1a; 3. 程序计数器&#xff08;一个线程可以…...

编程日记 2025/7/8 10:36:04

PVD中断检测掉电

文章目录 概述配置掉电擦写注意 概述 STM32 PVD功能具体可以检测到上电、掉电瞬间&#xff0c;其处理方式有中断响应及事件响应。掉电设置为上升沿触发&#xff0c;上电为下降沿触发 配置 1.开启PVD中断并设置其优先级 2.配置响应中断或事件的阈值电压 3.配置响应模式 生成…...

编程日记 2025/6/29 5:18:28

Nginx — 防盗链配置

防盗链简述 防盗链是一种保护网络资源所有者权益的技术手段&#xff0c;旨在防止未经授权的用户或网站通过直接链接的方式盗用资源&#xff0c;以下是关于防盗链的简述&#xff1a; 原理 基于请求头验证&#xff1a;服务器通过检查请求头中的特定字段&#xff0c;如Referer字…...

编程日记 2025/6/29 7:38:49

题解：P2485 [SDOI2011] 计算器

### 思路 本题是一个比较模板化的题目。 #### 一操作 考虑使用快速幂。 快速幂&#xff0c;只需要把 $k$ 变成二进制即可实现 $\Theta(\log k)$ 的时间复杂度。 实现方法&#xff1a; cpp long long qmi(long long a,long long k,long long p){ long long res 1; …...

编程日记 2025/6/29 6:13:15

【算法刷题笔记day one】滑动窗口（定长基础版）

前言 hello大家好呀 好久不见&#xff0c;上次更新是去年12月份的事情了。这段时间好好沉淀了一下&#xff0c;打了几场比赛&#xff0c;论文也写了一些&#xff0c;也收集了不少信息&#xff0c;对未来方向也有了不一样的计划。 这个算法系列可以说是接着我之前的数据结构系…...

编程日记 2025/6/29 6:55:07

Redis从入门到实战实战篇2

面试重点&#xff1a;本篇包含悲观锁&#xff0c;乐观锁&#xff0c;多线程以及分布式锁的知识 目录 3.优惠卷秒杀 3.1 -全局唯一ID 3.2 -Redis实现全局唯一Id 3.3 添加优惠卷 3.4 实现秒杀下单 3.5 库存超卖问题分析 3.6 乐观锁解决超卖问题 3.7 优惠券秒杀-一人一单 …...

编程日记 2025/6/29 7:53:44

代码随想录算法训练营Day43

力扣300.最长递增子序列 力扣674.最长连续递增子序列【easy】 力扣1143.最长公共子序列【medium】 力扣718.最长重复子数组【medium】 一、力扣300.最长递增子序列【medium】 题目链接&#xff1a;力扣300.最长递增子序列 视频链接&#xff1a;代码随想录 题解链接&#xff1a…...

编程日记 2025/6/29 6:15:12

Scrapy框架之【settings.py文件】详解

settings.py 文件的主要作用是对 Scrapy 项目的全局设置进行集中管理。借助修改这个文件中的配置项&#xff0c;你可以对爬虫的行为、性能、数据处理等方面进行灵活调整&#xff0c;而无需修改爬虫代码。 ①默认英文注释settings.py # Scrapy settings for douban project # …...

编程日记 2025/6/29 7:58:45

Nginx发布Vue（ElementPlus），与.NETCore对接（腾讯云）

案例资料链接&#xff1a;https://download.csdn.net/download/ly1h1/90745660 1.逻辑说明 1.1 逻辑示意图 # 前端请求处理逻辑图浏览器请求流程: 1. 浏览器发起请求├─ 开发环境(DEV)│ ├─ 请求URL: http://192.168.0.102:3000/api/xxx│ └─ 被Vite代理处理└─ 生产…...

编程日记 2025/6/29 7:25:10

深入探索 AAC 编码原理与 ADTS 格式：音频世界的智慧结晶

在数字音频的广阔领域中&#xff0c;AAC 编码及其相关的 ADTS 格式扮演着至关重要的角色。无论是在我们日常使用的音乐 APP&#xff0c;还是高清视频中的音频部分&#xff0c;都能看到它们的身影。今天&#xff0c;就让我们深入探索 AAC 编码原理与 ADTS 格式的奥秘&#xff0c…...

编程日记 2025/6/29 5:15:19

深度学习核心架构：探明四种基础神经网络

摘要 本文对多层感知机(MLP)、卷积神经网络(CNN)、循环神经网络(RNN)和注意力机制等深度学习核心架构的内部运作机制进行可视化分析。通过展示参数学习过程、激活映射和注意力分布等关键特征&#xff0c;揭示了"黑箱"模型的内部工作原理&#xff0c;为模型可解释性研…...

编程日记 2025/6/29 5:15:12

解析机器人 2.0.2 | 支持超过50种短视频平台的链接解析，无水印提取，多功能下载工具

解析机器人是一款功能强大的工具软件&#xff0c;登录即可解锁会员特权。它支持超过50种短视频平台的链接解析&#xff0c;包括抖音、快手、西瓜、bilibili等&#xff0c;并能实现无水印提取。此外&#xff0c;还提供P2P下载、磁力链等多种下载方式&#xff0c;确保用户能够快速…...

编程日记 2025/6/29 5:28:36

【漫话机器学习系列】237. TSS总平方和

深度理解 TSS&#xff08;总平方和&#xff09;&#xff1a;公式、意义与应用 在机器学习与统计建模领域&#xff0c;评价模型好坏的重要指标之一就是方差与误差分析。其中&#xff0c;TSS&#xff08;Total Sum of Squares&#xff0c;总平方和&#xff09;扮演着非常关键的角…...

编程日记 2025/7/18 4:39:17

flutter3.29 build.gradle.kts设置安卓签名

1、在android目录下创建key.properties文件 storePassword密码 keyPassword密码 keyAlias别名 storeFilejks文件完整路径 2、修改android/app/build.gradle.kts 顶部插入import java.util.Properties import java.io.FileInputStreamval keystoreProperties Properties() v…...

编程日记 2025/6/29 5:15:13

＜servlet-class＞和＜/url-pattern＞的作用

在 SpringMVC 的 web.xml 配置中&#xff0c;<servlet-class> 和 <url-pattern> 是两个关键配置项&#xff0c;分别用于指定处理请求的 Servlet 类和定义该 Servlet 拦截的请求路径规则。以下是它们的具体作用及原理分析&#xff1a; 一、<servlet-class> 的…...

编程日记 2025/7/15 5:37:36

linux部署的mysql数据库修改表名为小写配置

背景: 使用ruoyi-flowable框架初始化流程表结构时, 执行的sql语句创建的表名是大写。但mysql执行sql时大小写是敏感的 删除大写表 处理配置 使用mysql 8.0.41配置表名大小写敏感配置&#xff0c;需要初始化数据库 在MySQL 8.0及以上版本中&#xff0c;lower_case_table_names参…...

编程日记 2025/6/29 8:20:21

【Hot 100】94. 二叉树的中序遍历

目录 引言二叉树的中序遍历我的解题代码优化更清晰的表述建议&#xff1a; &#x1f64b;‍♂️ 作者&#xff1a;海码007&#x1f4dc; 专栏&#xff1a;算法专栏&#x1f4a5; 标题&#xff1a;【Hot 100】94. 二叉树的中序遍历❣️ 寄语&#xff1a;书到用时方恨少&#xff…...

编程日记 2025/6/29 5:26:44

基于D-Mixer与TransXNet的YOLOv8改进—融合全局-局部特征与空间降维注意力机制的CNN-ViT混合架构

随着目标检测任务对精度与效率要求的不断提升，传统的卷积神经网络(CNN)在建模长程依赖和复杂语义关系方面逐渐暴露出其局限性。而视觉Transformer(ViT)虽然在全局信息建模上表现优异，却因计算开销大、局部细节感知能力不足，在实时检测任务中难以直接部署。本文提出一种面向Y…...

编程日记 2025/7/18 4:38:38

《算法导论(第4版)》阅读笔记：p2-p3

《算法导论(第4版)》学习第 2 天&#xff0c;p2-p3 总结&#xff0c;总计 2 页。 一、技术总结 无。 二、英语总结(生词&#xff1a;1) 1.incremental (1) increase: in-(“in”) crescere “to grow” (2)increment (3)incremental: increment -al adj. incremental…...

编程日记 2025/7/9 4:15:39

基于Qlearning强化学习的电梯群控系统高效调度策略matlab仿真

目录 1.算法仿真效果 2.算法涉及理论知识概要 2.1 Q-learning强化学习原理 2.2 基于Q-learning的电梯群控系统建模 3.MATLAB核心程序 4.完整算法代码文件获得 1.算法仿真效果 matlab2022a仿真结果如下&#xff08;完整代码运行后无水印&#xff09;&#xff1a; 仿真操作…...

编程日记 2025/6/29 5:23:50

嵌入式硬件篇---STM32F103C8T6STM32F103RCT6

文章目录 前言一、相同点内核与主频基础外设开发环境 二、不同点1. 存储容量2. 外设资源3. 封装与引脚 三、代码移植注意事项1. 内存与 Flash 限制Flash差异RAM调整 2. 外设差异外设缺失&#xff1a;GPIO 映射&#xff1a; 3. 中断向量表中断向量偏移 4. 时钟与总线配置APB分频…...

编程日记 2025/7/14 21:36:06

rhce第二次作业

任务目标 1.配置ssh实现A&#xff0c;B主机互相免密登录 2.配置nginx服务&#xff0c;通过多ip区分多网站 任务一 关闭防火墙 [rootlocalhost ~]# setenforce 0 [rootlocalhost ~]# systemctl stop firewalld.service A主机免密登录B主机 ### A主机生成密钥 [rootlocalh…...

编程日记 2025/7/15 4:00:34

Linux第20节 --- inode和文件系统

一、没有被打开的文件 如果一个文件没有被打开&#xff0c;那么该文件存储在哪里&#xff1f; 该文件是存储在磁盘当中的&#xff01; 文件 文件内容 文件属性&#xff01; 文件的内容是按照数据块存储的&#xff1b;文件的属性其实就是inode&#xff08;是一个128字节的…...

编程日记 2025/6/29 5:17:45

LeetCode - 19.删除链表的倒数第N个结点

目录 题目 解法一 双指针算法 核心思想 执行流程 具体例子 代码 解法二 两次遍历法 核心思想 执行流程 具体例子 代码 题目 19. 删除链表的倒数第 N 个结点 - 力扣&#xff08;LeetCode&#xff09; 解法一 双指针算法 核心思想 利用双指针间隔固定距离(n1)&a…...

编程日记 2025/6/29 5:16:41

在 Ubuntu 上安装 cPanel

开始之前&#xff0c;请确保拥有一台 Ubuntu 服务器&#xff0c;推荐使用 Ubuntu 22.04 LTS。如果没有&#xff0c;可以查看免费服务器&#xff1a; 11个免费 VPS&#xff0c;够用一辈子了&#xff01;&#xff08;2025最新&#xff09;Top 11 免费VPS推荐平台对比&#xff08…...

编程日记 2025/6/29 5:15:20

《Linux macOS ：GCC升级方法》

GCC&#xff08;GNU Compiler Collection&#xff09;是广泛使用的编译器套件&#xff0c;升级到9以上版本可以获得更好的C17/20支持和性能优化。以下是不同Linux发行版和macOS的升级方法&#xff1a; Ubuntu/Debian 系统 添加工具链源 sudo apt update sudo apt install soft…...

编程日记 2025/6/29 7:38:04

C++ STL vector容器详解：从原理到实践

引言 亲爱的小伙伴们&#xff0c;今天我要和大家分享一个C编程中的"神器"——vector容器&#xff01;作为STL&#xff08;标准模板库&#xff09;中最常用的容器之一&#xff0c;vector就像是一个"超级数组"&#xff0c;既有数组的高效随机访问特性&#…...

编程日记 2025/7/18 4:41:11

[计算机网络]数据链路层

0 概论&#xff1a;数据链路层都干什么事&#xff0c;提供啥功能 比物理层再高一层就是数据链路层&#xff0c;咱们上一篇讲物理层&#xff0c;物理层直接接触传输介质&#xff0c;现在数据链路层是使用物理层的传输服务&#xff0c;然后实现更多的功能。物理层是只管把比特流…...

编程日记 2025/6/29 5:17:30

基于 vue-flow 实现可视化流程图

vue-flow 是一个基于 Vue.js 的强大且灵活的可视化流程图库&#xff0c;它允许开发者轻松创建交互式的流程图、工作流图、节点图等。 主要特点 易于使用 &#xff1a;提供了简洁的 API 和组件&#xff0c;开发者可以快速上手并创建复杂的流程图。高度可定制 &#xff1a;支持…...

编程日记 2025/6/29 5:15:18

【网络编程】HTTP(超文本传输协议)详解

&#x1f984;个人主页:修修修也 &#x1f38f;所属专栏:网络编程 ⚙️操作环境:Visual Studio 2022 目录 &#x1f4cc;HTTP定义 &#x1f4cc;HTTP工作原理 1.客户端发起请求: 2.服务器处理请求: 3.客户端处理响应: &#x1f4cc;HTTP关键特性 &#x1f38f;HTTP请求方法 &am…...

编程日记 2025/6/29 5:46:41

NuttX 与 PX4 系统开发全流程详解

NuttX 与 PX4 系统开发全流程详解 目录 1. NuttX 构建与使用2. NuttX 启动流程解析3. BootLoader 源码分析4. GPIO 驱动机制5. I2C 驱动分析6. PX4 系统架构简析7. uORB 消息机制8. PX4 应用开发示例9. 串口及 GPS 驱动解析10. MAVLink 协议与 PX4 交互 1. NuttX 构建与使用 …...

编程日记 2025/6/29 7:59:44

【Mytais系列】Myatis的设计模式

目录 设计模式 1. 工厂模式&#xff08;Factory Pattern&#xff09; 2. 建造者模式&#xff08;Builder Pattern&#xff09; 3. 动态代理模式&#xff08;Dynamic Proxy Pattern&#xff09; 4. 模板方法模式&#xff08;Template Method Pattern&#xff09; 5. 策略模…...

编程日记 2025/7/18 4:41:49

Linux：进程优先级及环境

一&#xff1a;孤儿进程 在Linux系统中&#xff0c;当一个进程创建了子进程后&#xff0c;如果父进程执行完毕或者提前退出而子进程还在运行&#xff0c;那么子进程就会成为孤儿进程。子进程就会被systemd&#xff08;系统&#xff09;进程收养&#xff0c;其pid为1 myproces…...

编程日记 2025/6/29 5:17:46

网络编程初识

注&#xff1a;此博文为本人学习过程中的笔记 1.socket api 这是操作系统提供的一组api&#xff0c;由传输层向应用层提供。 2.传输层的两个核心协议 传输层的两个核心协议分别是TCP协议和UDP协议&#xff0c;它们的差别非常大&#xff0c;编写代码的风格也不同&#xff0c…...

编程日记 2025/7/8 22:57:52

疾病传播模拟 ——python实操

1、需求 疾病传播模拟 定义一个Infection类，包含初始感染人数、每日感染率等属性，以及一个simulate_spread方法用于模拟疾病传播过程。 使用numpy随机生成初始感染人数（范围1-100）和每日感染率（范围0.01-0.1）。 创建Infection对象，模拟10天的疾病传播过程，每天计算感染…...

编程日记 2025/7/18 4:37:15

用docker ffmpeg测试视频vmaf分数，很快不用编译

之前测试vmaf要自己编译libvmaf&#xff0c;自己编译ffmpeg&#xff0c;巨麻烦&#xff0c;或者用老旧不再维护的docker仓库&#xff0c;最近在docker hub上发现了编译了libvmaf的ffmpeg的docker&#xff0c;而且镜像很小&#xff0c;适合直接运行。 # dest.mp4 评分视频&…...

编程日记 2025/6/29 7:18:34

【浅学】Windows下ffmpeg+nginx+flv将本地视频推流在本地搭建的Web前端页面中播放，超详细步骤

Nginx安装和配置 下载nginx-1.19.3-http-flv 模块预编译包并解压放在d盘&#xff0c;路径就跟安装步骤里说的一样(如下图)&#xff0c;不然会有其他问题出现。 打开conf/nginx.conf&#xff0c;查看RTMP和http相关的配置&#xff0c;确认端口号和路由名称 ffpemg推流视频…...

编程日记 2025/6/29 7:31:38

SQL笔记——左连接、右连接、内连接

前言&#xff1a;总是忘记表连接的区别&#xff0c;在面试的时候也容易被问到&#xff0c;因此就好记性不如烂笔头吧 集合运算 有并集、交集、差集 联合查询*&#xff08;针对行合并的&#xff09;* union为关键字&#xff0c;就是将两个select的结果求并集&#xff08;此时重…...

编程日记 2025/6/29 6:44:13

iOS启动优化：从原理到实践

前言 在iOS应用开发中&#xff0c;启动速度是影响用户体验的重要因素之一。研究表明&#xff0c;启动时间每增加1秒&#xff0c;用户留存率就会下降约7%。本文将深入探讨iOS启动优化的各个方面&#xff0c;从底层原理到具体实践&#xff0c;帮助开发者打造更快的应用启动体验。…...

编程日记 2025/7/15 16:24:44

202553-sql

目录 一、196. 删除重复的电子邮箱 - 力扣&#xff08;LeetCode&#xff09; 二、602. 好友申请 II &#xff1a;谁有最多的好友 - 力扣&#xff08;LeetCode&#xff09; 三、176. 第二高的薪水 - 力扣&#xff08;LeetCode&#xff09; 一、196. 删除重复的电子邮箱 - 力扣…...

编程日记 2025/6/29 6:13:01

Socket-TCP

在TCP/ip协议中&#xff0c;用源IP、源端口号、目的IP、目的端口号、协议号这样一个五元组来标识一个通信&#xff01; 端口号范围划分 0 - 1023: 知名端口号&#xff0c;HTTP&#xff0c;FTP&#xff0c;SSH 等这些广为使用的应用层协议&#xff0c;他们的端口号都是固定的。…...

编程日记 2025/6/29 8:23:14

BOSS的收入 - 华为OD机试（A卷，C++题解）

华为OD机试题库《C》限时优惠 9.9 华为OD机试题库《Python》限时优惠 9.9 华为OD机试题库《JavaScript》限时优惠 9.9 代码不懂有疑问欢迎留言或私我们的VX&#xff1a;code5bug。 题目描述 一个 XX 产品行销总公司&#xff0c;只有一个 boss&#xff0c;其有若干一级分销&…...

编程日记 2025/6/29 6:43:23