牛客网《BAT面试算法精品课》视频链接：《BAT面试算法精品课》 笔记链接： 牛客网《BAT面试算法精品课》笔记一：排序 牛客网《BAT面试算法精品课》笔记二：字符串 牛客网《BAT面试算法精品课》笔记三：队列和栈 牛客网《BAT面试算法精品课》笔记四：链表 牛客网《BAT面试算法精品课》笔记五：二分搜索 牛客网《BAT面试算法精品课》笔记六：二叉树 牛客网《BAT面试算法精品课》笔记七：位运算 牛客网《BAT面试算法精品课》笔记八：排列组合 牛客网《BAT面试算法精品课》笔记九：概率 牛客网《BAT面试算法精品课》笔记十：大数据 牛客网《BAT面试算法精品课》笔记十一：动态规划 01.在笔试面试中常作为客观问题出现（选择题） 02.在笔试中往往出现概率，期望的计算 03.往往利用古典概率进行计算（组合数学） 概率的应用： 01.利用随机来改进著名算法（快速排序） 02.随机数发生器（用给定的随机数发生器构造另一个） 案例一. 8支球队，有3个强队，随机把他们分成4组比赛，每组两个队，问两强相遇的概率是多大？ 案例二. 3只蚂蚁从正三角形的三个顶点沿着边移动，速度是相同的，问他们碰头的概率是多少？ 案例三. 某地区重男轻女，一个家庭如果生出一个女孩就一直生，直到生出男孩就停止生育。假设一胎只出生一个孩子，问时间足够长后，男女比例是会变为多少？ 案例四. 给定一个等概率随机产生15的随机函数，除此之外，不能使用任何额外的随机机制，请实现等概率随机产生17的随机函数。 案例五. 给定一个以p概率产生0，以1~p概率产生1的随机函数f()，p是固定的值，但你并不知道是多少。除此之外也不能使用任何额外的随机机制，请用f()实现等概率随机产生0和1的随机函数。 案例六. 解法： 案例七： 给定一个长度为N且没有重复元素的数组arr和一个整数M，实现函数等概率随机打印arr中的M个数。 每次找到一个数就打印，然后就跟数组最后一个没打印的元素交换。一直如此操作，直到打印够M个数. 案例八 举例 解法： 证明： i小于等于k时： i大于k时: