卡特兰数
文章目录
- 1、简介
- 1.1 何为卡特兰数
- 1.2 卡特兰数的通项公式
- 2、应用
- 2.1 题目1:括号合法
- 题目描述
- 思路分析
- 2.2 题目2:进出栈的方式
- 2.2.1 题目描述
- 2.2.2 思路分析
- 2.3 题目3:合法的序列
- 2.3.1 题目描述
- 2.3.2 思路分析
- 2.3.3 代码实现
- 2.4 题目4:不同二叉树的数量
- 2.4.1 题目描述
- 2.4.2 思路分析
- 2.4.3 代码实现
- 3、总结
1、简介
1.1 何为卡特兰数
卡特兰数又称卡塔兰数,英文名Catalan number,是组合数学 中一个常在各种计数问题中出现的数列。
前几项为:1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, …
1.2 卡特兰数的通项公式
k(0)=1,k(1)=1k(0) = 1, k(1) = 1k(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) = k(0) * k(n - 1) + k(1) * k(n - 2) + ... + k(n - 2) * k(1) + k(n - 1) * k(0)k(n)=k(0)∗k(n−1)+k(1)∗k(n−2)+...+k(n−2)∗k(1)+k(n−1)∗k(0)
或者
k(n)=C2nn−C2nn−1k(n) = C_{2n}^n- C_{2n}^{n-1}k(n)=C2nn−C2nn−1
或者
k(n)=C2nn/(n+1)k(n) = C_{2n}^n / (n + 1)k(n)=C2nn/(n+1)
就说这个表达式,满足卡特兰数,常用的是范式1和2,3几乎不会使用到
2、应用
2.1 题目1:括号合法
题目描述
给定 NNN 个左括号,NNN 个右括号,它们自由组合,必须全部使用,能得到多少个合法的组合?
思路分析
“合法”的定义是对于自由排列的组合,只要保证任意的前缀,右括号数量 ≤\le≤ 左括号数量,那么它最终一定是合法的。原理就是左括号比右括号多的时候,一旦出现右括号就能将多的左括号配对,最终一定会全部配对成功。反之则不行。
先讨论一个数学思想:如何确定两个集合相等
【集合A 和 集合B 可以是完全不相干的两个可数集合,只要能找到一个映射fff,使得A集合中的一个对应B集合中的一个,又能找到一个和 fff 毫不相干的映射 ggg 使得 B集合中的一个对应 A集合中的一个,如果存在这样一组映射,那么A集合数量和B集合数量一定相等。】
借此,来讨论括号组合的合法问题。合法的组合数量不好算,那就可以先选出不合法的组合数量,然后使用总的排列方法 减去 不合法的,就是合法的。
总的排列方法数为 C2nnC_{2n}^nC2nn,意思是一共 2n2n2n 个位置,选择其中的 nnn 个放左括号,剩下的 nnn 个位置放右括号。
而不合法的特征一定存在一个最初的前缀:右括号数量 = 左括号数量 + 1,如 ())(()
,最初前缀就是 ())
。那么在该前缀后的就是 右括号数量 + 1 = 左括号数量 (因为左右括号的数量相等)。以这个最初前缀为分界线,后面的所有括号进行反转,即右括号变成左括号,左括号变成右括号,就变成了())))(
,那么分界线后的左括号数量 + 1 = 右括号数量。如此一来,整体的 右括号数量 = 左括号数量 + 2。
定义两个集合,A集合放所有不合法的情况,B集合是 n+1n + 1n+1 个右括号,n−1n-1n−1个左括号 组合得到的所有情况 (该集合的来源不深究),也就是说通过上面的括号反转,A集合中任意一个不合法的元素通过该映射都能变出一个B集合的某一个元素;而B集合中的每个元素都能变成A集合其中的一个,如))))((
,最初的不合法前缀为)
,以该前缀为分界线后面的所有括号反转。最终得到)((())
。
所以 “nnn 个左括号 和 nnn 个右括号组合不合法的数量” = “n+1n+1n+1个右括号 和 n−1n-1n−1个左括号组合的所有数量”,即 C2nn+1C_{2n}^{n+1}C2nn+1。
所以,nnn 个左括号和 nnn 个右括号组合的合法数量 = C2nn−C2nn+1C_{2n}^{n} - C_{2n}^{n+1}C2nn−C2nn+1,而 C2nn+1=C2nn−1C_{2n}^{n+1} = C_{2n}^{n-1}C2nn+1=C2nn−1,因此合法的组合数量也可以是 C2nn−C2nn−1C_{2n}^n - C_{2n}^{n-1}C2nn−C2nn−1。
也就是说,括号类型的违规可以转换为卡特兰数进行计算,因为C2nn−C2nn−1C_{2n}^n - C_{2n}^{n-1}C2nn−C2nn−1 是卡特兰数的通项公式之一。
2.2 题目2:进出栈的方式
2.2.1 题目描述
nnn 个数字要进出栈,一共有多少种进出栈的方式?
2.2.2 思路分析
例如,给定数字[1, 2],进出栈的方式:
合法的情况:
1. 1进(↓),1出(↑),2进(↓),2出(↑)
2. 1进(↓),2进(↓),2出(↑),1出(↑)
只用记录箭头
不合法的情况:
1. ↑ ↑ ↓ ↓ (没有数字进栈是无法出栈的)
考察箭头组合的合法数量,这其实就是括号问题。进栈是左括号,出栈是右括号。合法的条件就是在任何时候,右括号数量不能大于左括号数量,也就是任意时刻出栈次数 ≤\le≤ 进栈次数就是合法的进出栈方式,就是卡特兰数。
再举个例子:某个公司的股票有上涨和下跌,问有多少种交易方式可以使得股票不会跌到X轴以下?
这也是一个卡特兰数问题,往上就是左括号,往下就是右括号,就是在问左右括号合理的结合方式。
2.3 题目3:合法的序列
2.3.1 题目描述
假设给你 NNN 个 0,和 NNN 个 1,你必须用全部数字拼序列。
返回有多少个序列满足:任何前缀串,1的数量都不少于0的数量
2.3.2 思路分析
这个就是 “括号合法” 模型问题,1是左括号,0是右括号,任意时刻满足左括号数量 ≥\ge≥ 右括号数量。
直接使用卡特兰数的通项公式解决即可。
2.3.3 代码实现
import java.util.LinkedList;public class 10Ways {//方法1:暴力递归public static long ways1(int N) {int zero = N;int one = N;LinkedList<Integer> path = new LinkedList<>();LinkedList<LinkedList<Integer>> ans = new LinkedList<>();process(zero, one, path, ans);long count = 0;for (LinkedList<Integer> cur : ans) {int status = 0;for (Integer num : cur) {if (num == 0) {status++;} else {status--;}if (status < 0) {break;}}if (status == 0) {count++;}}return count;}public static void process(int zero, int one, LinkedList<Integer> path, LinkedList<LinkedList<Integer>> ans) {if (zero == 0 && one == 0) {LinkedList<Integer> cur = new LinkedList<>();for (Integer num : path) {cur.add(num);}ans.add(cur);} else {if (zero == 0) {path.addLast(1);process(zero, one - 1, path, ans);path.removeLast();} else if (one == 0) {path.addLast(0);process(zero - 1, one, path, ans);path.removeLast();} else {path.addLast(1);process(zero, one - 1, path, ans);path.removeLast();path.addLast(0);process(zero - 1, one, path, ans);path.removeLast();}}}//方法2:卡特兰数的通项公式解决public static long ways2(int N) {if (N < 0) {return 0;}if (N < 2) {return 1;}long a = 1;long b = 1;long limit = N << 1;for (long i = 1; i <= limit; i++) {if (i <= N) {a *= i;} else {b *= i;}}return (b / a) / (N + 1);}public static void main(String[] args) {System.out.println("test begin");for (int i = 0; i < 10; i++) {long ans1 = ways1(i);long ans2 = ways2(i);if (ans1 != ans2) {System.out.println("Oops!");}}System.out.println("test finish");}
}
2.4 题目4:不同二叉树的数量
2.4.1 题目描述
有 NNN 个二叉树节点,每个节点彼此之间无任何差别。返回由 NNN 个二叉树节点,组成的不同结构数量是多少?
2.4.2 思路分析
如果 0 个节点,只能组成空树,1种;
如果 1 个节点,只能组成1个节点的树,1种;
如果 2 个节点,只有2种结构。
n 个节点组成二叉树的情况:
1)第 1 种划分:头结点1个,左子树0个,右子树 n−1n-1n−1 个
在这种划分下,不同结构的数量为:[0个节点组成的方法数] ×\times× [n−1n-1n−1个节点组成的方法数]
2)第 2 种划分:头结点左边1个节点,右边 n−2n-2n−2 个节点
在这种划分下,不同结构的数量为:[1个节点组成的方法数] ×\times× [n−2n-2n−2个节点组成的方法数]
这个规律就是卡特兰数的第1个通项公式,所以这就是卡特兰数。 那么直接用卡特兰数的第2个通项公式计算即可,因为卡特兰数的三个通项公式是等效的。
2.4.3 代码实现
public class DifferentBTNum {// 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) / (n + 1)
// 或者
// k(n) = c(2n, n) - c(2n, n-1)//方法1public static long num1(int N) {if (N < 0) {return 0;}if (N < 2) {return 1;}long[] dp = new long[N + 1];dp[0] = 1;dp[1] = 1;for (int i = 2; i <= N; i++) {for (int leftSize = 0; leftSize < i; leftSize++) {dp[i] += dp[leftSize] * dp[i - 1 - leftSize];}}return dp[N];}//方法2:卡特兰数public static long num2(int N) {if (N < 0) {return 0;}if (N < 2) {return 1;}long a = 1;long b = 1;for (int i = 1, j = N + 1; i <= N; i++, j++) {a *= i;b *= j;long gcd = gcd(a, b);a /= gcd;b /= gcd;}return (b / a) / (N + 1);}public static long gcd(long m, long n) {return n == 0 ? m : gcd(n, m % n);}public static void main(String[] args) {System.out.println("test begin");for (int i = 0; i < 15; i++) {long ans1 = num1(i);long ans2 = num2(i);if (ans1 != ans2) {System.out.println("Oops!");}}System.out.println("test finish");}
}
3、总结
- 要对卡特兰数的通项公式1和公式2烂熟于心;
- 对“括号合法”模型(左右括号数量相等的合法性问题)要有敏感度;
- 加强对卡特兰数通项公式1的敏感度的训练,如题目4,符合公式1等同于公式2,而通常可能是写出了暴力递归才会发现公式1,就要求对暴力解法有了解。
补充:
数学结论:所有整数和所有偶数数量相等。因为任何整数乘以2后等于某个偶数,而任意偶数除以2后等于某个整数,二者建立了一一映射关系,所以整数数量和偶数数量就是一样多的。在数学上,它叫作“等势”。
5米的线和10米的线上的点数量一样多。在两条线之外找某一个定点,5米线上找任意一个点和定点连线能对应到10米中的一个点,10米的任意一个点和定点连线能对应到5米中的一个点,所以5米的线和10米的线点一样多。
点是无长度的,无长度的东西有可能有无限个点。更多可以查看希尔伯特旅馆悖论。
总而言之,牵扯到一个非常重要的思想,两个可数集合A和B,能互相建立一种映射关系,那它们的数量就是一样多的。
相关文章:

卡特兰数
文章目录1、简介1.1 何为卡特兰数1.2 卡特兰数的通项公式2、应用2.1 题目1:括号合法题目描述思路分析2.2 题目2:进出栈的方式2.2.1 题目描述2.2.2 思路分析2.3 题目3:合法的序列2.3.1 题目描述2.3.2 思路分析2.3.3 代码实现2.4 题目4…...

分布式任务处理
分布式任务处理 1. 什么是分布式任务调度 视频上传成功需要对视频的格式进行处理,如何用Java程序对视频进行处理呢?这里有一个关键的需求就是当视频比较多的时候我们如何可以高效处理。 如何去高效处理一批任务呢? 1、多线程 多线程是充…...
Linux 命令复习
常用命令 1、目录操作 cd 切换目录 cd / 切换到根目录 cd ~ 回到个人用户的主目录 ls 查看当前目录下所有文件的详细信息 list的意思 ll 查看当前目录下所有文件的详细信息 pwd 显示当前目录的全路径 . …...
leetcode 困难 —— 天际线问题(优先队列)
(思路感觉挺明显的,就是一些特殊情况得考虑清楚) 题目: 城市的 天际线 是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。给你所有建筑物的位置和高度,请返回 由这些建筑物形成的 天际线 。 每个建筑物的几何信息…...

离散数学笔记_第一章:逻辑和证明(2 )
1.2 命题逻辑的应用1.2.1 语句翻译 1.2.2 系统规范说明 1.2.3 布尔搜索 1.2.4 逻辑谜题泥巴孩子谜题骑士和流氓(考研逻辑题)1.1.2.5 逻辑电路1.2.1 语句翻译 🐳为啥要翻译语句? ➡因语言常常有二义性(有歧义&#x…...

MFCC语音特征值提取算法
博主简介 博主是一名大二学生,主攻人工智能研究。感谢让我们在CSDN相遇,博主致力于在这里分享关于人工智能,c,Python,爬虫等方面知识的分享。 如果有需要的小伙伴可以关注博主,博主会继续更新的,…...
TencentOS3.1编译安装redis6.2.5
下载地址:https://redis.io/download 最近版为7.0.8,本次安装的是6.2.5 软件包解包并进入目录。 redis是c语言编写的,编译需要gcc,按网上资料说默认安装的gcc版本过低(可能是4.8.5),使用rpm …...
AI顶会accepted papers list
为方便相关paper调研,对相关顶会文章列表和下载地址汇总,会议包括:AAAI、ACL、IJCAI、ICLR、COLING、SIGIR、WSDM、WWW、ICML、KDD、NeurIPS、CVPR、ECCV、ACM MM 2023 Accepted papers list 更新于:(2022.11.24&…...

IOS逆向之frida安装
首先手机要越狱,这个就不说了,博主就是咸鱼搞了个160的苹果6, 自己刷到苹果6支持最新的12.5.7版本后越狱; 谁让他低版本,不支持 CrackerXI砸壳呢,当时你要是使用 frida-ios-dump 也是可以的; …...
《金山区提信心扩需求稳增长促发展行动方案》的通知
金发改规〔2023〕1号 各镇政府、街道办事处、园区管委会,区政府各部门、各直属单位: 《金山区提信心扩需求稳增长促发展行动方案》已经区委、区政府同意,现印发给你们,请认真按照执行。 附件:金山区提信心扩需求稳增…...

【Redis】Java客户端JedisSpringDataRedis入门(三)
🚗Redis学习第三站~ 🚩起始站:【Redis】概述&环境搭建(一) 🚩本文已收录至专栏:数据库学习之旅 👍希望您能有所收获 在上一篇中我们学习了Redis常见命令的使用,显然,我们不可能一…...

挑选销售自动化工具应该关注什么功能?
销售自动化可以极大地提高你的生产力和效率,每周都为你节省时间。这样,你就可以把更多的时间用于完成交易,而减少用于行政任务的时间。市面上的销售自动化工具有很多,作为一般经验法则,以下是销售自动化工具中需要寻找…...

thread.join 是干什么的?原理是什么?
Thread.join 加了join,表示join的线程的修改对于join之外的代码是可见的。 代码示例: public class JoinDemo {private static int i 1000;public static void main(String[] args) {new Thread(()->{i 3000;}).start();System.out.println("…...

论文阅读 | Cross-Attention Transformer for Video Interpolation
前言:ACCV2022wrokshop用transformer做插帧的文章,q,kv,来自不同的图像 代码:【here】 Cross-Attention Transformer for Video Interpolation 引言 传统的插帧方法多用光流,但是光流的局限性在于 第一&…...

【C++修炼之路】22.哈希
每一个不曾起舞的日子都是对生命的辜负 哈希一.哈希概念及性质1.1 哈希概念1.2 哈希冲突1.3 哈希函数二.哈希冲突解决2.1 闭散列/开放定址法2.2 开散列/哈希桶三.开放定址法代码3.1 插入Insert3.2 查找Find3.3 删除Erase3.4 映射的改良&完整代码四.开散列代码4.1 插入Inser…...

HashMap原理(一):哈希函数的设计
目录导航哈希函数的作用与本质哈希函数设计哈希表初始容量的校正哈希表容量为2的整数次幂的缺陷及解决办法注:为了简化代码,提高语义,本文将HashMap很多核心代码抽出并根据代码含义为代码片段取名,完全是为了方便读者理解。哈希函…...

06--WXS 脚本
1、简介WXS(WeiXin Script)是小程序的一套脚本语言,结合 WXML ,可以构建出页面的结构。 注意事项WXS 不依赖于运行时的基础库版本,可以在所有版本的小程序中运行。WXS 与 JavaScript 是不同的语言,有自己的…...

【Vue3】vue3 + ts 封装城市选择组件
城市选择-基本功能 能够封装城市选择组件,并且完成基础的显示隐藏的交互功能 (1)封装通用组件src/components/city/index.vue <script lang"ts" setup name"City"></script> <template><div class…...

C语言if判断语句的三种用法
C if 语句 一个 if 语句 由一个布尔表达式后跟一个或多个语句组成。 语法 C 语言中 if 语句的语法: if(boolean_expression) {/* 如果布尔表达式为真将执行的语句 */ }如果布尔表达式为 true,则 if 语句内的代码块将被执行。如果布尔表达式为 false&…...
React中echarts的封装
做大屏的时候经常会遇到 echarts 展示 在 React (^18.2.0) 中对 echarts (^5.4.0) 的简单封装 echarts 封装使用 props 说明 参数说明类型可选值默认值opts初始化传入的 opts https://echarts.apache.org/zh/api.html#echarts…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)
HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

CMake基础:构建流程详解
目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...
条件运算符
C中的三目运算符(也称条件运算符,英文:ternary operator)是一种简洁的条件选择语句,语法如下: 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true,则整个表达式的结果为“表达式1”…...

基于Docker Compose部署Java微服务项目
一. 创建根项目 根项目(父项目)主要用于依赖管理 一些需要注意的点: 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件,否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...
【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分
一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计,提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合:各模块职责清晰,便于独立开发…...
大学生职业发展与就业创业指导教学评价
这里是引用 作为软工2203/2204班的学生,我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要,而您认真负责的教学态度,让课程的每一部分都充满了实用价值。 尤其让我…...

GC1808高性能24位立体声音频ADC芯片解析
1. 芯片概述 GC1808是一款24位立体声音频模数转换器(ADC),支持8kHz~96kHz采样率,集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器,适用于高保真音频采集场景。 2. 核心特性 高精度:24位分辨率,…...
蓝桥杯 冶炼金属
原题目链接 🔧 冶炼金属转换率推测题解 📜 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V,是一个正整数,表示每 V V V 个普通金属 O O O 可以冶炼出 …...

Mysql中select查询语句的执行过程
目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析(Parser) 2.4、执行sql 1. 预处理(Preprocessor) 2. 查询优化器(Optimizer) 3. 执行器…...