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

LeetCode096不同的二叉搜索树(相关话题:卡特兰数)

目录

题目描述

解题思路

代码实现

进出栈序列理解卡特兰数分析策略

相关知识

参考文章


题目描述

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

示例 1:

输入:n = 3
输出:5

示例 2:

输入:n = 1
输出:1

解题思路

题目要求是计算不同二叉搜索树的个数。为此,我们可以定义两个函数:

G(n): 长度为 n 的序列能构成的不同二叉搜索树的个数。

F(i,n) 以 i为根、序列长度为 n 的不同二叉搜索树个数 (1≤i≤n)。

可见,G(n) 是我们求解需要的函数。

稍后我们将看到,G(n)可以从 F(i,n)得到,而 F(i,n)又会递归地依赖于 G(n)。

首先,根据上一节中的思路,不同的二叉搜索树的总数 G(n),是对遍历所有 i (1≤i≤n)的 F(i,n) 之和。换言之:

公式一

  G\left ( n \right ) \sum_{i=1}^{n}F(i,n) 

对于边界情况,当序列长度为 1(只有根)或为 0(空树)时,只有一种情况,即:
G(0)=1,G(1)=1
给定序列 1⋯n,我们选择数字 i 作为根,则根为 i的所有二叉搜索树的集合是左子树集合和右子树集合的笛卡尔积,对于笛卡尔积中的每个元素,加上根节点之后形成完整的二叉搜索树,如下图所示:

二叉搜索树左节点<根结点<右节点

 因此,我们可以得到以下公式:

公式二

F(i,n)=G(i−1)⋅G(n−i)

 将公式一二 结合,可以得到 G(n的递归表达式:

   G\left ( n \right ) \sum_{i=1}^{n}G(i-1,n) G(n-i,n)
 

事实上我们在方法一中推导出的 G(n)函数的值在数学上被称为卡塔兰数  

 卡塔兰数更便于计算的定义如下:

代码实现

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

进出栈序列理解卡特兰数分析策略

这是一道最经典的入门级卡特兰数题目,如果能把这题看懂,相信后面的题目也能迎刃而解。

题目

n 个元素进栈序列为:1,2,3,4,...,n,则有多少种出栈序列?

思路

我们将进栈表示为 +1,出栈表示为 -1,则 1 3 2 的出栈序列可以表示为:+1 -1 +1 +1 -1 -1。

根据栈本身的特点,每次出栈的时候,必定之前有元素入栈,即对于每个 -1 前面都有一个 +1 相对应。因此,出栈序列的所有前缀和必然大于等于 0,并且 +1 的数量等于 -1 的数量。

接下来让我们观察一下 n = 3 的一种出栈序列:+1 -1 -1 +1 -1 +1。序列前三项和小于 0,显然这是个非法的序列。

如果将第一个前缀和小于 0 的前缀,即前三项元素都进行取反,就会得到:-1 +1 +1 +1 -1 +1。此时有 3 + 1 个 +1 以及 3 - 1 个 -1。

因为这个小于 0 的前缀和必然是 -1,且 -1 比 +1 多一个,取反后,-1 比 +1 少一个,则 +1 变为 n + 1 个,且 -1 变为 n - 1 个。进一步推广,对于 n 元素的每种非法出栈序列,都会对应一个含有 n + 1 个 +1 以及 n - 1 个 -1 的序列。

如何证明这两种序列是一一对应的?

假设非法序列为 A,对应的序列为 B。每个 A 只有一个"第一个前缀和小于 0 的前缀",所以每个 A 只能产生一个 B。而每个 B 想要还原到 A,就需要找到"第一个前缀和大于 0 的前缀",显然 B 也只能产生一个 A。

把A小于0的前缀后部分取反,其余部分不变

每个 B 都有 n + 1 个 +1 以及 n - 1 个 -1,因此 B 的数量为 \textrm{C}_{2n}^{n+1}相当于在长度为 2n 的序列中找到 n + 1 个位置存放 +1。相应的,非法序列的数量也就等于\textrm{C}_{2n}^{n+1}​。
 出栈序列的总数量共有\textrm{C}_{2n}^{n},因此,合法的出栈序列的数量为\textrm{C}_{2n}^{n} - \textrm{C}_{2n}^{n+1} = \frac{\textrm{C}_{2n}^{n} }{n+1}

此时我们就得到了卡特兰数的通项 \frac{\textrm{C}_{2n}^{n} }{n+1}

相关知识

img

顺便提一下,这里f(0)=1,

但是看表达式的话x=0是没定义的,

所以这里是极限意义上的,

然后补充该点定义即可,

再详细的细节就不深究了...

可以验证极限是否是1:

令1-4x=t   那么\lim_{t \to 1} \frac{1-\sqrt{t}}{\frac{1-t}{2}} = \lim_{t \to 1} \frac{1}{\frac{1+\sqrt{t}}{2}} =1 

当  x\geq \frac{1}{2}  时 的泰勒展开公式:

这个通项看起来太不和谐了,

还是再整理一下吧:

参考文章

由递推式求catalan数列通项公式

「算法入门笔记」卡特兰数

不同的二叉搜索树

相关文章:

LeetCode096不同的二叉搜索树(相关话题:卡特兰数)

目录 题目描述 解题思路 代码实现 进出栈序列理解卡特兰数分析策略 相关知识 参考文章 题目描述 给你一个整数 n &#xff0c;求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种&#xff1f;返回满足题意的二叉搜索树的种数。 示例 1&#xff1a; …...

软件测试7

一 CS和BS软件架构 CS&#xff1a;客户端-服务器端&#xff0c;BS&#xff1a;浏览器端-服务器端 区别总结&#xff1a; 1.效率&#xff1a;c/s效率高&#xff0c;某些内容已经安装在系统中了&#xff0c;b/s每次都要加载最新的数据 2.升级&#xff1a;b/s无缝升级&#xff0c…...

12 结构:如何系统设计框架的整体目录?

到现在&#xff0c;我们已经将 Gin 集成到框架 hade 中&#xff0c;同时又引入了服务容器和服务提供者&#xff0c;明确框架的核心思想是面向服务编程&#xff0c;一切皆服务&#xff0c;所有服务都是基于协议。后续也会以服务的形式&#xff0c;封装一个个的服务&#xff0c;让…...

假如你知道这样的MySQL性能优化

1. 为查询缓存优化你的查询 大多数的 MySQL 服务器都开启了查询缓存。这是提高性最有效的方法之 一&#xff0c;而且这是被 MySQL 的数据库引擎处理的。当有很多相同的查询被执行了多次的时候&#xff0c;这些查询结果会被放到一个缓存中&#xff0c;这样&#xff0c;后续的相同…...

79、ClimateNeRF: Physically-based Neural Rendering for Extreme Climate Synthesis

简介主页物理模拟可以很好地预测天气影响。神经辐射场产生SOTA场景模型。ClimateNeRF 允许我们渲染真实的天气效果&#xff0c;包括雾霾、雪和洪水 &#xff0c;结果可以通过有物理意义的变量来控制&#xff0c;比如水位 &#xff0c;这允许人们可视化气候变化的结果将对他们产…...

前端面试题(一)

目录 前言 一、css3实现布局的方式有哪些&#xff1f; 1.flex布局 2.grid布局 二、jquery的扩展机制&#xff1f; 三、jquery动画和css实现动画的本质区别&#xff1f; 四、不使用css的动画&#xff0c;如何实现盒子从左到右移动&#xff1f; 五、使用过的框架&#xf…...

Java基础常见面试题(七)

序列化和反序列化 Java序列化与反序列化是什么&#xff1f; Java序列化是指把Java对象转换为字节序列的过程&#xff0c;而Java反序列化是指把字节序列恢复为Java对象的过程。 序列化&#xff1a; 序列化是把对象转换成有序字节流&#xff0c;以便在网络上传输或者保存在本地…...

【springmvc】报文信息转换器

HttpMessageConverter HttpMessageConverter&#xff0c;报文信息转换器&#xff0c;将请求报文转换为Java对象&#xff0c;或将Java对象转换为响应报文 HttpMessageConverter提供了两个注解和两个类型&#xff1a; RequestBody&#xff0c; ResponseBody&#xff0c; Reques…...

3.5知识点复习

extern&#xff1a;表示声明。 没有内存空间。 不能提升。const&#xff1a;限定一个变量为只读变量。volatile&#xff1a;防止编译器优化代码。volatile int flg 0; register&#xff1a;定义一个寄存器变量。没有内存地址。register int a 10;字符串&#xff1a;C语言中&a…...

湖南中创教育PMP分享项目经理有哪些优势?

项目经理拥有超强的计划能力&#xff1b;具备大局意识&#xff1b;沟通能力特别强&#xff1b;具备更大的灵活性和反应能力以及总结汇报能力 1、超强的计划能力 项目经理几乎无时无刻都在做计划&#xff0c;因此也就更擅长做计划。 项目管理要抓重点&#xff0c;有主次地处理…...

LeetCode:27. 移除元素

给你一个数组 nums 和一个值 val&#xff0c;你需要 原地 移除所有数值等于 val 的元素&#xff0c;并返回移除后数组的新长度。 不要使用额外的数组空间&#xff0c;你必须仅使用 O(1) 额外空间并 原地 修改输入数组。 元素的顺序可以改变。你不需要考虑数组中超出新长度后面…...

麻雀算法SSA优化LSTM长短期记忆网络实现分类算法

1、摘要 本文主要讲解&#xff1a;麻雀算法SSA优化LSTM长短期记忆网络实现分类算法 主要思路&#xff1a; 准备一份分类数据&#xff0c;数据介绍在第二章准备好麻雀算法SSA&#xff0c;要用随机数据跑起来用lstm把分类数据跑起来将lstm的超参数交给SSA去优化优化完的最优参数…...

哈希表题目:数组中的 k-diff 数对

文章目录题目标题和出处难度题目描述要求示例数据范围解法思路和算法代码复杂度分析题目 标题和出处 标题&#xff1a;数组中的 k-diff 数对 出处&#xff1a;532. 数组中的 k-diff 数对 难度 4 级 题目描述 要求 给定一个整数数组 nums\texttt{nums}nums 和一个整数 k…...

SAP ERP系统PP模块计划策略2050详解

SAP/ERP系统中面向订单生产的计划策略主要有20和50两个策略&#xff0c;这两个策略都是面向订单生产的计划策略&#xff0c;也是离散制造行业应用比较广泛的策略。它们之间最大差异就是在于20策略完全是由订单驱动&#xff0c;而50策略是预测加订单驱动&#xff0c;本文主要介绍…...

TIA博途中将硬件目录更改为中文的具体方法演示

TIA博途中将硬件目录更改为中文的具体方法演示 基本步骤可参考如下: 第一步: 第二步: 具体的操作演示: 如下图所示,在所示的目录中找到zh-chs文件夹,删除或修改文件夹的名称均可,这里建议大家修改文件夹的名称,防止以后需要恢复成英文目录, 如下...

【多线程操作】线程池模拟实现

目录 一.线程池的作用 二.线程池的模拟实现 1.线程模块&#xff08;Thread.hpp&#xff09;&#xff1a; 2.线程锁模块&#xff08;LockGuard.hpp&#xff09;&#xff1a; 3.任务模块&#xff08;Task.hpp&#xff09; 4.线程池核心&#xff08;ThreadPool.hpp&#xff…...

HBase---Hbase安装(单机版)

Hbase安装单机版 文章目录Hbase安装单机版Master/Slave架构安装步骤配置Hbase1.上传压缩包解压更名修改hbase-env.sh修改hbase-site.xml配置HBase环境变量配置Zookeeper复制配置文件修改zoo.cfg配置文件修改myid配置Zookeeper环境变量刷信息配置文件启动hbase步骤hbase shellMa…...

启动项管理工具Autoruns使用实验(20)

实验目的 &#xff08;1&#xff09;了解注册表的相关知识&#xff1b; &#xff08;2&#xff09;了解程序在开机过程中的自启动&#xff1b; &#xff08;3&#xff09;掌握Autoruns在注册表和启动项方面的功能&#xff1b;预备知识 注册表是windows操作系统中的一个核心数据…...

BFD单臂回声实验详解

13.1.1BFD概念 BFD提供了一个通用的、标准化的、介质无关的、协议无关的快速故障检测机制,有以下两大优点: 对相邻转发引擎之间的通道提供轻负荷、快速故障检测。 用单一的机制对任何介质、任何协议层进行实时检测。 BFD是一个简单的“Hello”协议。两个系统之间建立BFD会…...

详解JAVA类加载器

目录 1.概述 2.双亲委派 3.ServiceClassLoader 4.URLClassLoader 5.加载冲突 1.概述 概念&#xff1a; 类加载器&#xff08;Class Loader&#xff09;是Java虚拟机&#xff08;JVM&#xff09;的一个重要组件&#xff0c;负责加载Java类到内存中并使其可以被JVM执行。类…...

19c补丁后oracle属主变化,导致不能识别磁盘组

补丁后服务器重启&#xff0c;数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后&#xff0c;存在与用户组权限相关的问题。具体表现为&#xff0c;Oracle 实例的运行用户&#xff08;oracle&#xff09;和集…...

反向工程与模型迁移:打造未来商品详情API的可持续创新体系

在电商行业蓬勃发展的当下&#xff0c;商品详情API作为连接电商平台与开发者、商家及用户的关键纽带&#xff0c;其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息&#xff08;如名称、价格、库存等&#xff09;的获取与展示&#xff0c;已难以满足市场对个性化、智能…...

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现

摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序&#xff0c;以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务&#xff0c;提供稳定高效的数据处理与业务逻辑支持&#xff1b;利用 uniapp 实现跨平台前…...

(一)单例模式

一、前言 单例模式属于六大创建型模式,即在软件设计过程中,主要关注创建对象的结果,并不关心创建对象的过程及细节。创建型设计模式将类对象的实例化过程进行抽象化接口设计,从而隐藏了类对象的实例是如何被创建的,封装了软件系统使用的具体对象类型。 六大创建型模式包括…...

人工智能 - 在Dify、Coze、n8n、FastGPT和RAGFlow之间做出技术选型

在Dify、Coze、n8n、FastGPT和RAGFlow之间做出技术选型。这些平台各有侧重&#xff0c;适用场景差异显著。下面我将从核心功能定位、典型应用场景、真实体验痛点、选型决策关键点进行拆解&#xff0c;并提供具体场景下的推荐方案。 一、核心功能定位速览 平台核心定位技术栈亮…...

图解JavaScript原型:原型链及其分析 | JavaScript图解

​​ 忽略该图的细节&#xff08;如内存地址值没有用二进制&#xff09; 以下是对该图进一步的理解和总结 1. JS 对象概念的辨析 对象是什么&#xff1a;保存在堆中一块区域&#xff0c;同时在栈中有一块区域保存其在堆中的地址&#xff08;也就是我们通常说的该变量指向谁&…...

高分辨率图像合成归一化流扩展

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 1 摘要 我们提出了STARFlow&#xff0c;一种基于归一化流的可扩展生成模型&#xff0c;它在高分辨率图像合成方面取得了强大的性能。STARFlow的主要构建块是Transformer自回归流&#xff08;TARFlow&am…...

用神经网络读懂你的“心情”:揭秘情绪识别系统背后的AI魔法

用神经网络读懂你的“心情”:揭秘情绪识别系统背后的AI魔法 大家好,我是Echo_Wish。最近刷短视频、看直播,有没有发现,越来越多的应用都开始“懂你”了——它们能感知你的情绪,推荐更合适的内容,甚至帮客服识别用户情绪,提升服务体验。这背后,神经网络在悄悄发力,撑起…...

内窥镜检查中基于提示的息肉分割|文献速递-深度学习医疗AI最新文献

Title 题目 Prompt-based polyp segmentation during endoscopy 内窥镜检查中基于提示的息肉分割 01 文献速递介绍 以下是对这段英文内容的中文翻译&#xff1a; ### 胃肠道癌症的发病率呈上升趋势&#xff0c;且有年轻化倾向&#xff08;Bray等人&#xff0c;2018&#x…...

2025-05-08-deepseek本地化部署

title: 2025-05-08-deepseek 本地化部署 tags: 深度学习 程序开发 2025-05-08-deepseek 本地化部署 参考博客 本地部署 DeepSeek&#xff1a;小白也能轻松搞定&#xff01; 如何给本地部署的 DeepSeek 投喂数据&#xff0c;让他更懂你 [实验目的]&#xff1a;理解系统架构与原…...