牛客网《BAT面试算法精品课》视频链接：《BAT面试算法精品课》 笔记链接： 牛客网《BAT面试算法精品课》笔记一：排序 牛客网《BAT面试算法精品课》笔记二：字符串 牛客网《BAT面试算法精品课》笔记三：队列和栈 牛客网《BAT面试算法精品课》笔记四：链表 牛客网《BAT面试算法精品课》笔记五：二分搜索 牛客网《BAT面试算法精品课》笔记六：二叉树 牛客网《BAT面试算法精品课》笔记七：位运算 牛客网《BAT面试算法精品课》笔记八：排列组合 牛客网《BAT面试算法精品课》笔记九：概率 牛客网《BAT面试算法精品课》笔记十：大数据 牛客网《BAT面试算法精品课》笔记十一：动态规划 题目分类： 01.以高中数学为基础的古典概率计算方法 02.斐波那契数和卡特兰数 03.以选择题居多 案例一 在6乘9的方格中，以左上角为起点，右下角为终点，每次只能向下走或者向右走，请问一共有多少种不同的走法。[

](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042201-300x71.png)](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042201.png) **案例二** ABCDEFG七人站队，要求A必须站在B的左边，但不要求一定相邻，请问共有多少种排法？第二问如果要求A必须站在B的左边，并且一定要相邻，请问一共有多少种排法？ 问题一：[![](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042202-300x213.png)](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042202.png) 问题二：[![](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042203-300x164.png)](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042203.png) **案例三：** 六个人排成一排，要求甲与乙不相邻，并且甲与丙不相邻的排法数是多少？ 方法一： 甲乙相邻总数：[![](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042204-300x158.png)](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042204.png) 最终结果[![](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042205-300x197.png)](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042205.png) 方法二：[![](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042206-300x262.png)](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042206.png) **案例四：** 10颗相同的糖果，分给3个人，每人至少一颗，问有多少种分法。[![](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042207-300x139.png)](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042207.png) **案例五：** 10个不同的球放入3个不同的桶里有多少种方法？[![](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042208-300x233.png)](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042208.png) **案例六：** 有10颗糖，如果每天至少吃一颗，吃完为止，问有多少种不同的吃法？[![](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042209-300x218.png)](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042209.png) **案例七：** 假设有n对左右括号，请求出合法的排列有多少个？合法是指每一个括号都可以找到与之配对的括号，比如n=1时，()是合法的，但是)(为不合法[![](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042210-300x174.png)](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042210.png) [![](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042211-300x126.png)](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042211.png) [![](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042212-300x61.png)](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042212.png) 卡特兰数公式：[![](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042213-300x89.png)](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042213.png) **案例八：** N个数进出栈的顺序有哪些？假设栈的容量无限大。再补充一个问题，2n个人排队买票，n个人拿10块钱，票价是5块钱一张，每个人买一张票，售票员手里没有零钱，问有多少种排队方法让售票员可以顺利卖票。 5块钱相当于左括号，10块钱相当于右括号，解法还是和案例七一样 **案例九：** 求n个无差别的节点构成的二叉树有多少种不同的结构？[![](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042214-300x135.png)](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042214.png) [![](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042215-300x169.png)](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042215.png) 卡特兰数重要公式2：[![](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042216-300x145.png)](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042216.png) **案例十：** 12个高矮不同的人，排成两排，每排必须是从矮到高排列，而且第二排比对应的第一排的人高，问排列方式有多少种？ [![](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042217-300x248.png)](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042217.png) **案例十一：** 有n个信封，包含n封信，现在把信拿出来，再装回去，要求每封信不能装回它原来的信封，问有多少种装法？[![](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042218-300x117.png)
](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042201-300x71.png)](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042201.png) **案例二** ABCDEFG七人站队，要求A必须站在B的左边，但不要求一定相邻，请问共有多少种排法？第二问如果要求A必须站在B的左边，并且一定要相邻，请问一共有多少种排法？ 问题一：[![](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042202-300x213.png)](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042202.png) 问题二：[![](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042203-300x164.png)](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042203.png) **案例三：** 六个人排成一排，要求甲与乙不相邻，并且甲与丙不相邻的排法数是多少？ 方法一： 甲乙相邻总数：[![](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042204-300x158.png)](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042204.png) 最终结果[![](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042205-300x197.png)](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042205.png) 方法二：[![](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042206-300x262.png)](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042206.png) **案例四：** 10颗相同的糖果，分给3个人，每人至少一颗，问有多少种分法。[![](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042207-300x139.png)](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042207.png) **案例五：** 10个不同的球放入3个不同的桶里有多少种方法？[![](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042208-300x233.png)](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042208.png) **案例六：** 有10颗糖，如果每天至少吃一颗，吃完为止，问有多少种不同的吃法？[![](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042209-300x218.png)](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042209.png) **案例七：** 假设有n对左右括号，请求出合法的排列有多少个？合法是指每一个括号都可以找到与之配对的括号，比如n=1时，()是合法的，但是)(为不合法[![](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042210-300x174.png)](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042210.png) [![](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042211-300x126.png)](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042211.png) [![](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042212-300x61.png)](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042212.png) 卡特兰数公式：[![](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042213-300x89.png)](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042213.png) **案例八：** N个数进出栈的顺序有哪些？假设栈的容量无限大。再补充一个问题，2n个人排队买票，n个人拿10块钱，票价是5块钱一张，每个人买一张票，售票员手里没有零钱，问有多少种排队方法让售票员可以顺利卖票。 5块钱相当于左括号，10块钱相当于右括号，解法还是和案例七一样 **案例九：** 求n个无差别的节点构成的二叉树有多少种不同的结构？[![](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042214-300x135.png)](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042214.png) [![](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042215-300x169.png)](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042215.png) 卡特兰数重要公式2：[![](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042216-300x145.png)](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042216.png) **案例十：** 12个高矮不同的人，排成两排，每排必须是从矮到高排列，而且第二排比对应的第一排的人高，问排列方式有多少种？ [![](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042217-300x248.png)](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042217.png) **案例十一：** 有n个信封，包含n封信，现在把信拿出来，再装回去，要求每封信不能装回它原来的信封，问有多少种装法？[![](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042218-300x117.png)