【LeetCode】不同的二叉搜索树 [M](卡特兰数)
96. 不同的二叉搜索树 - 力扣(LeetCode)
一、题目
给你一个整数 n
,求恰由 n
个节点组成且节点值从 1
到 n
互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。
示例 1:
输入:n = 3 输出:5
示例 2:
输入:n = 1 输出:1
提示:
1 <= n <= 19
二、代码
class Solution {public int numTrees(int n) {return compute(n);}public int compute(int N) {// 过滤特殊值if (N < 0) {return 0;}if (N < 2) {return 1;}long a = 1;long b = 1;long c = 0;// 2nlong limit = N << 1;// 1、计算c(2N, N) = b / afor (long j = 1, i = N + 1; j <= N && i <= limit; j++, i++) {// 计算a:从1累乘到na *= j;// 计算b:从n+1一直累乘到2n b *= i;// 求a和b的最大公因数,用来对a和b进行分数化简,避免在计算过程中溢出。// 如果这里不进行化简的话,当N比较大的时候就会出现数据溢出情况c = gcd(a, b);a /= c;b /= c; }// 2、计算公式3的计算结果// 公式3:k(n)= c(2n, n) / (n + 1)// c(n, m) = n(n-1)...(n-m+1) / m!// b:2n * (2n - 1) * ... * (2n - n + 1) 也就是从n+1一直累乘到2n// a:1 * 2 * ... * (n - 1) * n 也就是从1一直累乘到n// c(2N, N) = b / areturn (int) ((b / a) / (N + 1));}// 辗转相除法求最大公因数public long gcd(long a, long b) {long c = a % b;if (c != 0) {return gcd(b, c);} else {return b;}}
}
三、解题思路
卡特兰数满足如下关系式:
k(0)= 1, k(1)= 1时,如果接下来的项满足:
k(n)= k(0)*k(n-1) + k(1)*k(n- 2) + ... + k(n- 2)*k(1) + k(n- 1)* k(0)
或者
k(n)= C(2n, n) - C(2n, n-1)
或者
k(n)= C(2n, n) / (n + 1)
就说这个表达式,满足卡特兰数。
总的来说,需要剖析出这道题的本质:
假设n个节点存在二叉排序树的个数是G(n),1为根节点,2为根节点,...,n为根节点,当1为根节点时,其左子树节点个数为0,右子树节点个数为n-1,同理当2为根节点时,其左子树节点个数为1,右子树节点为n-2,所以可得G(n) = G(0)*G(n-1)+G(1)*(n-2)+...+G(n-1)*G(0)。
明白了这道题的本质,发现了这个计算式子,就马上意识到这是一个卡特兰数的题目,直接用卡特兰数的计算公式计算结果即可。
相关文章:
![](https://img-blog.csdnimg.cn/img_convert/646a44edefeb3ed073dfd17c19e3168e.jpeg)
【LeetCode】不同的二叉搜索树 [M](卡特兰数)
96. 不同的二叉搜索树 - 力扣(LeetCode) 一、题目 给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。 示例 1: 输入:n 3 输出&a…...
![](https://img-blog.csdnimg.cn/faeb4e1cf7204a77aa5ef5415584bf7e.png#pic_center)
【软件相关】文献管理工具——Zotero
文章目录0 前期教程1 前言2 一些说明3 下载安装4 功能一:插入文献引用格式5 功能二:从网页下载文献pdf和题录6 功能三:数据多平台同步7 功能四:通过DOI添加条目及添加订阅8 安装xpi插件9 功能五:智能识别中英文文献10 …...
![](https://img-blog.csdnimg.cn/5f7643a7e62149a3874d15f309fbdb6b.gif#pic_center)
leetcode练习一:数组(二分查找、双指针、滑动窗口)
文章目录一、 数组理论基础二、 二分查找2.1 解题思路2.2 练习题2.2.1 二分查找(题704)2.2.2 搜索插入位置(题35)2.2.3 查找排序数组元素起止位置(题34)2.2.4 有效的完全平方数(题367)2.2.5 x 的平方根&…...
![](https://img-blog.csdnimg.cn/img_convert/843b86ef8e6bf7a58bac4aefa7b04820.png)
iPhone更新iOS 16.3出现应用卡死、闪退的问题怎么办?
在升级最新的 iOS 16.3 系统后,有些用户可能遇到了个别应用无法正常打开,卡死的异常情况。大家可以尝试通过如下方式解决问题。 1.重新启动应用: 如果应用出现卡死或闪退,可从 iPhone 屏幕由底往上滑(或连续按两次 H…...
![](https://img-blog.csdnimg.cn/3c896f46f261420cafe389aca07959e2.png)
TCP协议原理一
文章目录一、TCP协议二、TCP工作机制1.确认应答2.超时重传3.连接管理三次握手四次挥手一、TCP协议 我们的TCP协议相比于UDP协议复杂不少,今天我们就来一起学习一下TCP协议报文和原理 首先我们报头第一行里的端口号和UDP的端口号是一致的,都是用两个字节…...
![](https://img-blog.csdnimg.cn/ce427b65706440759114a3e2930cde91.png)
【黑马SpringCloud(6)】Sentinel解决雪崩问题
微服务保护雪崩问题服务保护技术Sentinel微服务整合Sentinel流量控制簇点链路入门练习流控模式关联链路流控效果Warm Up排队等待热点参数限流隔离和降级FeignClient整合Sentinel线程隔离(舱壁模式)实现线程隔离熔断降级慢调用异常比例/异常数授权规则获取origin给网关添加请求头…...
![](https://img-blog.csdnimg.cn/77175a42b3794fa485bfd450de530519.jpeg)
微信小程序 java springboot招聘求职应聘简历系统
应聘系统是基于微信小程序,java编程语言,mysql数据库,springboot框架,idea工具开发,本系统主要分为用户,企业,管理员三个角色,用户注册登陆小程序,查看应聘分类ÿ…...
![](https://img-blog.csdnimg.cn/6ed63a984c03455b9e6f2841964fcc6c.gif)
亿级高并发电商项目-- 实战篇 --万达商城项目 四(Dashboard服务、设置统一返回格式与异常处理、Postman测试接口 )
专栏:高并发---前后端分布式项目 👏作者简介:大家好,我是小童,Java开发工程师,CSDN博客博主,Java领域新星创作者 📕系列专栏:前端、Java、Java中间件大全、微信小程序、…...
![](https://img-blog.csdnimg.cn/e9f4105a773a4e2a9b813f951f62a0e1.png)
为什么这11道JVM面试题这么重要(附答案)
本文内容整理自 博学谷狂野架构师 运行时数据区都包含什么 虚拟机的基础面试题 程序计数器Java 虚拟机栈本地方法栈Java 堆方法区 程序计数器 程序计数器是线程私有的,并且是JVM中唯一不会溢出的区域,用来保存线程切换时的执行行数 程序计数器ÿ…...
![](https://img-blog.csdnimg.cn/2ac9383429744fe99d407f42a1b9912f.png#pic_center)
概率统计之概率篇
概率统计之概率篇 一 随机变量及其四种研究方法 为了更深入地研究随机现象,需要把随机试验的结果数量化,也就是要引进随机变量来描述随机试验的结果。 一般地,把表示随机现象的各种结果或描述随机事件的变量叫做随机变量。随机变量通常用大…...
![](https://img-blog.csdnimg.cn/img_convert/87eae43f42b85cc92ed3bf61a3b70024.png)
综合项目 旅游网 【5.旅游线路收藏功能】
分析判断当前登录用户是否收藏过该线路当页面加载完成后,发送ajax请求,获取用户是否收藏的标记根据标记,展示不同的按钮样式编写代码后台代码RouteServlet/*** 判断当前登录用户是否收藏过该路线*/ public void isFavorite(HttpServletReques…...
![](https://csdnimg.cn/release/blog_editor_html/release2.2.3/ckeditor/plugins/CsdnLink/icons/icon-default.png?t=N176)
【ArcGIS Pro二次开发】(3):UI管理_显示隐藏Tab、Group、Control等控件
在ArcGIS Pro工作中,有时候会涉及到工具栏UI的管理,比如,打开模型构建器时,工具栏才会出现新的选项卡(Tab)【ModelBuilder】,工程未做更改,则【保存】按钮显示灰色不可用。 下面以一个小例子来学习一下。 一…...
![](https://img-blog.csdnimg.cn/ef365995c8ca404eae83b3136f86599e.png)
Spring Boot开发实战——echarts图标填充数据
echarts模块的导入 先看看成品吧! 有的图标的数据用了一些计算框架不是直接查数据库所以有点慢。 ok!😃 上正文,接上节Spring boot项目开发实战——(LayUI实现前后端数据交换与定义方法渲染数据)讲解了一般…...
![](https://www.ngui.cc/images/no-images.jpg)
李达聪老师:互联网时代的B2B品牌如何塑造
李达聪老师:互联网时代的B2B品牌如何塑造互联网时代企业对企业的品牌如何塑造?互联网时代信息传播速度加快,并且各大新品牌就如春天的竹笋涌出,有的昙花一现,有的趁着时代的红利乘胜追击占领市场,建立品牌。有的成为一…...
![](https://img-blog.csdnimg.cn/443d2c4a1de64ca08f54b355fa0d0ab3.png#pic_center)
javaEE 初阶 — 连接管理机制
文章目录连接管理机制1. 建立连接(三次握手)2. 断开连接(四次挥手)TCP 的工作机制确认应答机制 超时重传机制 连接管理机制 比如 主机A 的空间存储了 主机B 的 ip 和 端口,主机B 的空间存储了 主机A 的 ip 和 端口。…...
![](https://img-blog.csdnimg.cn/img_convert/9bfd522e407fdf7c6d8820f3a095bd00.jpeg)
40个改变你编程技能的小技巧!
40个改变编程技能的小技巧 1、将大块代码分解成小函数 2、今日事今日毕,如果没毕,就留到明天。 如果下班之前还没有解决的问题,那么你需要做的,就是关闭电脑,把它留到明天。 中途不要再想着问题了! 3、…...
![](https://img-blog.csdnimg.cn/img_convert/8c932f035e27ee03fdbe85764d59ec54.jpeg)
iTOP3588开发板直连电脑配置方法(无线上网)配置主机IP
首先使用网线连接好主机和开发板,在没有上电的情况下,可以看到以太网显示网络电缆 被拔出,如下图所示: 当开发板上电以后,开发板网卡与笔记本电脑的网卡会连接,如下图所示: 然后右键点击以太网…...
![](https://img-blog.csdnimg.cn/4a5d3e14e38e4ba28fa4e43074b73a97.png)
压电陶瓷换能器导纳圆图公式推导及匹配
压电陶瓷换能器的等效电路图如下图所示,分为左右两个部分左边的电容和电阻并联构成了电路的静态支路,被称为静态电容,可以由电表很方便的测量得到,这部分的参数是由换能器的电学参数决定的。右边的串联构成了动态支路,…...
![](https://img-blog.csdnimg.cn/f2346807130743cd9d41e4e48bae02c7.png)
设计模式C++实现11:观察者模式
参考大话设计模式; 详细内容参见大话设计模式一书第十四章,该书使用C#实现,本实验通过C语言实现。 观察者模式又叫做发布-订阅(Publish/Subscribe)模式。 观察者模式定义了一种一对多的依赖关系,让多个观察…...
![](https://img-blog.csdnimg.cn/1019c824786c4f08b937c6a86f4b6c43.png)
l1和l2接口如何进行编写?一定要掌握这几个元素
在这个大数据时代,很多地方都需要用到l1和l2接口,l1和l2接口在应用程序与数据库之间起着桥梁的作用,是实现数据的整合与共享的重要帮手。 l1和l2接口适用于各行各业,应用场景的不断拓展,l1和l2接口的发展也兴起&#…...
![](https://img-blog.csdnimg.cn/4f0f4ac8f2a14f698b02df1e70ff221e.png)
GAMES101作业7及课程总结(重点实现多线程加速,微表面模型材质)
目录闲言碎语最终全部效果展示(均为10241024512ssp)课程总结与理解(Path Tracing)框架梳理任务一:迁移相关代码任务二:实现path tracing任务三:多线程加速(包括其他加速的小trick&am…...
![](https://img-blog.csdnimg.cn/img_convert/0de1a1822e07cb0e0331d7dd080367d4.png)
面试题(二十四)数据结构与算法
9.1哈希 请谈一谈,hashCode() 和equals() 方法的重要性体现在什么地方? 考察点:JAVA哈希表 参考回答: Java中的HashMap使用hashCode()和equals()方法来确定键值对的索引,当根据键获取值的时候也会用到这两个方法。…...
![](https://img-blog.csdnimg.cn/955654ec860b4ec5b818c4aa3e663b4b.png)
【HAL库】STM32CubeMX开发----STM32F407----Uart串口接收空闲中断
一、Uart串口接收空闲中断----详解 首先介绍串口通信的数据传输方式,这样后面的Uart串口空闲中断能更好的理解。 Uart串口通信----数据传输方式 串口通信的数据由发送设备通过自身的TXD接口传输到接收设备得RXD接口。 一个字符一个字符地传输,每个字符…...
![](https://www.ngui.cc/images/no-images.jpg)
Qt_文件操作
本文包含以下内容: 文件操作 基本介绍:ini文件:csv文件:代码功能文件读写:1.1 读取文件1.1.1按行读取1.1.2整体读取1.2 写入文件2. 文件信息读取3. 文件夹的创建4. 获取文件夹下所有的文件5. 获取文件夹及子文件夹下所有的文件用树的方式在界面显示文件夹目录基本介绍: …...
![](https://img-blog.csdnimg.cn/6f94b6980af8457cbbcccc868c3c5ca7.jpeg#pic_center)
int和Integer有什么区别?
第7讲 | int和Integer有什么区别? Java 虽然号称是面向对象的语言,但是原始数据类型仍然是重要的组成元素,所以在面试中,经常考察原始数据类型和包装类等 Java 语言特性。 今天我要问你的问题是,int 和 Integer 有什么…...
![](https://img-blog.csdnimg.cn/e3b6af7db74040ebb2d787be6974767a.png)
Axure 9 收录不同效果的制作过程
效果类别 一、默认选中实现单选效果 1、默认选中 点击组件,右键选择selected字样; 2、实现单选效果 点击所有组件,右键选择selected group,填好命名,并设置选中时的组件样式;选择其中一个组件…...
![](https://img-blog.csdnimg.cn/cb1bc7afbc1147f0a69bd09549825de3.png)
[Datawhale][CS224W]图神经网络(一)
目录一、导读1.1 当前图神经网络的难点1.2 图神经网络应用场景及对应的相关模型:1.3 图神经网络的应用方向及应用场景二、图机器学习、图神经网络编程工具参考文献一、导读 传统深度学习技术,如循环神经网络和卷积神经网络已经在图像等欧式数据和信号…...
![](https://www.ngui.cc/images/no-images.jpg)
【Android实现16位灰度图数据转RGB数据并以bitmap格式显示】
Android实现16位灰度图数据转RGB数据并以bitmap显示(单通道Gray数据转三通道RGB数据并显示) 需求发现问题解决方案需求 问题需求:项目上需要实现将深度相机传感器给出的数据实时显示出来的功能。经过了解得知,传感器给出的数据为16位灰度图数据,即16位数据表示一个像素的…...
![](https://img-blog.csdnimg.cn/4d432331da334e8cbf6f4fd8f78a7860.jpeg#pic_center)
uni-app②
文章目录二、微信小程序简介(一)文档相关开发者工具使用小程序代码构成小程序基本操作三、uniapp 开发规范uniapp 开发环境开发工具下载 HBuilderX工程搭建项目运行浏览器运行四、组件基础组件基础组件列表组件公共属性集合扩展组件自定义组件UNI-ICON五…...
![](https://www.ngui.cc/images/no-images.jpg)
FFmpeg视频处理
目录 1. Ubuntu(wsl)安装 ffmpeg 2. ffmpeg查看指令 3. ffmpeg查看媒体文件信息 4. ffmpeg基础操作指令 5. ffmpeg视频抽帧 5.1 基于时间抽取帧 5.2 两种抽帧方式 5.3 视频流抽帧 5.4 视频批量抽帧 6. ffmpeg更改视频播放速度 7. ffmpeg视频格…...
![](/images/no-images.jpg)
做外贸没有企业网站/济南seo的排名优化
ArcGisOracle10gR2多数据库实例下SDE的服务安装方法首先要感谢来自c s d n博客“s w f c s u n b o y”(h t t p://b l o g.c s d n.n e t/s w f c s u n b o y/a r c h i v e/2007/10/09/18161 41.a s p x)和百度空间的“灰色的天空,灰色的心情”(h t t p://h i.b …...
![](http://shumeipai.nxez.com/wp-content/uploads/2017/02/20170207145829868-0.jpg)
注册网站公司/潍坊seo按天收费
MySQL占用内存太大,而SQLite是一款轻量级零配置数据库,非常适合在树莓派和其他嵌入式系统中使用。SQLite文档详细资料丰富,本文不会详细解释SQLite数据库操作的方方面面,只能结合具体场景按需说明。本文介绍的SQLite技巧也可以在其…...
![](https://images2015.cnblogs.com/blog/822713/201510/822713-20151015151659444-1943127463.png)
字体网站/云南省最新疫情情况
经过查阅资料和自己的理解整理出来的,欢迎大家指教。Awake和Start对比awake比start先执行。当有多个类的时候,所有类的awake执行完了才会执行start。awake里面一般放初始化的属性值,获取组件等。start里面可以处理一些只执行一次的功能。比如…...
![](https://img-blog.csdnimg.cn/img_convert/67d0865f17d9be527254bf8a8ff6c5b4.gif)
新开传奇网站单职业/推广平台排行榜app
一、NDK中获取android设备ID的方式Java代码如下(获取设备ANDROID_ID):final String androidId Secure.getString(context.getContentResolver(), Secure.ANDROID_ID);对应的c代码(相当蛋疼),注意如果是C,需要把所有的(*env)->替换成env-&…...
![](/images/no-images.jpg)
dw怎么做打开网站跳出提示/策划推广
1.下载搜狗拼音词库 wget http://hslinuxextra.googlecode.com/files/sougou-phrases-full.7z 2.用sougou-phrases-full.7z中的ibus/android.db文件替换/usr/share/ibus-pinyin/db/android.db文件。 转载于:https://www.cnblogs.com/tswcypy/p/3930848.html...
![](/images/no-images.jpg)
做网站的公司怎么赚钱/谷歌浏览器免费入口
话说省选也过去好几天了……按照oi届传统补个游记吧……这可能是我第一次写游记…… DAY -n 省选之前超级心慌……于是出去培训……首先到长沙并且成功抱到了几个大佬的大腿,在那里的模拟赛非常不稳每次写题都有暴力写挂,接着马不停蹄去了杭州二中然后体…...