当前位置: 首页 > 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执行。类…...

C++_核心编程_多态案例二-制作饮品

#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为&#xff1a;煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例&#xff0c;提供抽象制作饮品基类&#xff0c;提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...

Java 语言特性(面试系列1)

一、面向对象编程 1. 封装&#xff08;Encapsulation&#xff09; 定义&#xff1a;将数据&#xff08;属性&#xff09;和操作数据的方法绑定在一起&#xff0c;通过访问控制符&#xff08;private、protected、public&#xff09;隐藏内部实现细节。示例&#xff1a; public …...

VB.net复制Ntag213卡写入UID

本示例使用的发卡器&#xff1a;https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

Leetcode 3577. Count the Number of Computer Unlocking Permutations

Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接&#xff1a;3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯&#xff0c;要想要能够将所有的电脑解锁&#x…...

关于 WASM:1. WASM 基础原理

一、WASM 简介 1.1 WebAssembly 是什么&#xff1f; WebAssembly&#xff08;WASM&#xff09; 是一种能在现代浏览器中高效运行的二进制指令格式&#xff0c;它不是传统的编程语言&#xff0c;而是一种 低级字节码格式&#xff0c;可由高级语言&#xff08;如 C、C、Rust&am…...

MySQL账号权限管理指南:安全创建账户与精细授权技巧

在MySQL数据库管理中&#xff0c;合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号&#xff1f; 最小权限原则&#xf…...

Python 包管理器 uv 介绍

Python 包管理器 uv 全面介绍 uv 是由 Astral&#xff08;热门工具 Ruff 的开发者&#xff09;推出的下一代高性能 Python 包管理器和构建工具&#xff0c;用 Rust 编写。它旨在解决传统工具&#xff08;如 pip、virtualenv、pip-tools&#xff09;的性能瓶颈&#xff0c;同时…...

在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案

这个问题我看其他博主也写了&#xff0c;要么要会员、要么写的乱七八糟。这里我整理一下&#xff0c;把问题说清楚并且给出代码&#xff0c;拿去用就行&#xff0c;照着葫芦画瓢。 问题 在继承QWebEngineView后&#xff0c;重写mousePressEvent或event函数无法捕获鼠标按下事…...

android13 app的触摸问题定位分析流程

一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...

Linux部署私有文件管理系统MinIO

最近需要用到一个文件管理服务&#xff0c;但是又不想花钱&#xff0c;所以就想着自己搭建一个&#xff0c;刚好我们用的一个开源框架已经集成了MinIO&#xff0c;所以就选了这个 我这边对文件服务性能要求不是太高&#xff0c;单机版就可以 安装非常简单&#xff0c;几个命令就…...