• 阿里的两道和卡特兰数相关的面试题

    卡特兰数的使用
    服务器君一共花费 14.499 ms 进行了 4 次数据库查询,努力地为您提供了这个页面。
    广告很萌的

    卡特兰数前面介绍了概念和推导,那么怎么使用呢?我们来看看一道淘宝的面试题。

    问题描述:

    12个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种?

    我们先把这12个人从低到高排列,然后选择6个人排在第一排,那么剩下的6个肯定是在第二排。

    用0表示对应的人在第一排,用1表示对应的人在第二排,那么含有6个0,6个1的序列,就对应一种方案。

    比如000000111111就对应着

    • 第一排:0 1 2 3 4 5
    • 第二排:6 7 8 9 10 11

    010101010101就对应着

    • 第一排:0 2 4 6 8 10
    • 第二排:1 3 5 7 9 11

    问题转换为,这样的满足条件的01序列有多少个。

    观察1的出现,我们考虑这一个出现能不能放在第二排,显然,在这个1之前出现的那些0,1对应的人。要么是在这个1左边,要么是在这个1前面。而肯定要有一个0的,在这个1前面,统计在这个1之前的0和1的个数。

    也就是要求,0的个数大于1的个数。OK,问题已经解决。

    如果把0看成入栈操作,1看成出栈操作,就是说给定6个元素,合法的入栈出栈序列有多少个。

    这就是catalan数,这里只是用于栈,等价地描述还有,二叉树的枚举、多边形分成三角形的个数、圆括弧插入公式中的方法数,其通项是c(2n, n)/(n+1)。

    6个元素,合法序列,也就是 h(6) = C(6,12) - C(5,12)。

    C(6,12) = 12! / (6! * 6!) = 924, C(5,12) = 12! / (5! * 7!) = 792,所以 h(6) = 132。有132种排法。

    2015年阿里巴巴面试题也有一道和卡特兰数有关的题:

    一个合法的表达式由()包围,()可以嵌套和连接,如(())()也是合法 表达式;现在有 6 对(),它们可以组成的合法表达式的个数为____

    这个模型就不用分析了吧,很明显是卡特兰数,项为6。c(2n,n)-c(2n,n+1)=924-792=132。

    PS: c(2n, n)/(n+1) = c(2n, n) - c(2n, n-1)

更多 推荐条目

Welcome to NowaMagic Academy!

现代魔法 推荐于 2013-02-27 10:23   

本章最新发布
随机专题
  1. [软件工程与项目管理] 呈现器的布局与绘制 11 个条目
  2. [智力开发与知识管理] 整体性学习步骤 9 个条目
  3. [PHP程序设计] CodeIgniter与PHP框架设计 5 个条目
  4. [JavaScript程序设计] jQuery与表单操作 2 个条目
  5. [Python程序设计] Tornado表单处理 3 个条目
  6. [智力开发与知识管理] 信息的类型与结构 9 个条目
  7. [软件工程与项目管理] 开始使用Git 3 个条目
  8. [移动开发] Android Studio里的Gradle 3 个条目
  9. [移动开发] Android加载器Loaders 5 个条目
  10. [移动开发] Android与SQLite数据库 7 个条目
  11. [移动开发] 刷机与root相关 2 个条目
  12. [移动开发] Android View注入框架Butter Knife 3 个条目
窗口 -- [协会]