作者 | 梁唐
出品 | 公众号：Coder梁（ID：Coder_LT）
大家好，我是梁唐。
我们接着上篇继续来看B站2021校招的算法笔试题。
题目来源于牛客网，感兴趣的同学可以点击阅读原文跳转。
第一题
有一楼梯共10级，若每次只能跨上一级或二级，要走上第10级，共有多少走法？
动态规划原题，我们假设x级楼梯有f(x)种走法，显然f(0) = f(1) = 1。对于大于1的x来说，它可以有两种来源，一个是x-1，第二个是x-2。所以我们可以得到递推式f(x) = f(x-1) f(x-2)。
按照递推式推算一下可知：f(2)=2, f(3)=3, f(4)=5, f(5)=8, f(6)=13, f(7)=21, f(8)=34, f(9)=55, f(10)=89，所以答案选D。
不难发现这是斐波那契数列，我们也可以根据通项公式推算，通项公式为：
第二题
已知一棵有2011个结点的树，其叶节点个数为116，该树对应的二叉树无右孩子的结点个数为（）。
这道题有些坑，老梁上来也没看懂。看了好几遍题目，才终于明白它的意思。
首先我们看题目中说的是一棵有2011个节点的树，注意并没有明确指出是二叉树，在这种情况下这是一棵普通的树。然后题目中的说法是它对应的二叉树，这里就很奇怪了，树怎么对应二叉树呢？
其实这里隐藏的信息是树转二叉树算法，树转二叉树的逻辑倒不复杂，只有一个操作，对于树上的每一个节点，我们将它的第一个孩子节点当做它的左孩子，将它的右兄弟当做它的右孩子。如此一来，我们可以完成转化。
我从网上找来了一个例子，大家可以看下下图：
那这样转换之后我们怎么知道哪些节点没有右孩子节点呢？
我们还是需要从转换的算法上入手，由于我们在转换二叉树时是将右兄弟变成右孩子，所以没有右孩子的节点对应的就是转换之前没有右兄弟的节点。问题就变成了要求原树当中有多少个节点没有右兄弟。
到这里很多人就蒙圈了，这怎么求？
其实有办法求，并且还很简单。已知我们一共有2011个树节点，其中116个是叶子节点。众所周知叶子节点即没有孩子节点的节点，也就是说有2011-116个节点拥有孩子节点。很明显，对于每个拥有孩子节点的节点来说，它一定有且只有一个孩子节点没有右兄弟，即最右边那个。那么很显然，一共有2011-116=1895个节点没有右兄弟。
别忘了根节点也没有右兄弟，所以要加上根节点的1，答案就是1896。
第三题
100个人编号为1到100，按从小到大的顺序排队上飞机，每个人都应该坐到自己编号对应的座位上。不巧的是，第一个人是个疯子，会随机找一个座位坐下。对于后面的第二个人到第一百个人，若这个人编号对应的座位已经被别人给坐了，那这个人就会在剩下的座位中随机找一个座位坐下；若这个人编号对应的座位还是空的，那这个人就会正常地对号入座。最后一个人能坐上自己座位的概率是多少？
这是一道数学题，我们直接来算比较复杂。
首先我们来分析一下问题，对于第一个人来说，假设他随机选择的位置是k。那么我们可以知道，对于2到k-1的位置来说，都是没有被占据的。发生混乱的位置除了1以为一定都大于k，因为当k随机选择的时候，2到k-1的位置都已经被人占了。
有了这个结论之后，我们可以考虑一般情况。我们假设对于第k个人来说，轮到他的时候k位置被前面人占据的概率是f(k)。考虑k 1人的情况，求f(k 1)。
对于第k 1个人来说，他的位置可能被前面1-k的人占据。我们分别考虑这每一种情况，首先被1占据的概率，这个很明确就是frac 1 n ，其次是被2占据的概率。这有一个前提，就是2的位置首先得被占据，在此前提下，2占据k 1位置的概率是frac 1 {n-1} ，再乘上2被占据本身的概率f(2)。同样对于被3占据的概率来说，前提是3位置已经被占据了，其次3选择了k 1的位置，概率就是f(3)*frac 1 {n-2} ，以此类推，我们可以写出公式：
看起来好像没什么用，我们可以做一个小小的变形，我们可以发现前面k项加起来就是f(k) ，所以可以写成f(k 1) = f(k) f(k)*frac 1 {n-k 1} 我们可以套入公式简单来算几个值，可以得到f(2) = frac 1 {100}, f(3) = frac 1 {100} frac 1 {100} * frac{1}{99} = frac 1 {99} 。
不妨可以猜测，当i大于2时，f(i) = frac 1 {n - i 2} 。我们可以用数学归纳法来证明，显然i=2时成立，假设i=k时也成立，尝试证明i=k 1。
得证，所以f(100) = frac 1 {100 - 100 2} = 0.5 ，故选D。
这是比较扎实的数学推导的方法，也有巧妙的思路。还是考虑k 1的情况，我们可以从k的情况入手。假设第k个人的位置被占了，然后随机选了k 1，概率是f(k)*frac 1 {n-k 1} 。第二种情况是k的位置没有被占，是之前的乘客占了k 1的位置。此时k 1个乘客，有一个位置确定。因此等价于k乘客位置被占的情况，也就是f(k) ，所以f(k 1) = f(k) f(k)*frac{1}{n-k 1} 。
对于第二种情况，很多同学可能会觉得还需要乘上k乘客位置没有被占的概率1-f(k) ，但其实不必。因为k之前有乘客占了k 1的位置，k乘客位置一定没有被占。
第四题
b站有100万个up主 ,今天有100万用户随机且独立的给up主们投币,普通up主小明得到至少一枚硬币的概率和下面哪个值更接近?
100w个up主，有100w枚硬币，至少得到一枚的概率也就是一枚都得不到的反面。
每次投币当中得不到硬币的概率是1-1/100w，100w次都得不到的概率就是frac {999999} {1000000} ^{1000000} 。这个概率很明显很难直接计算，我们可以采用泊松分布来进行估算。其中lambda = np = 1 ，套入泊松分布公式，可以得到：
那么X等于0的概率约等于0.633，故选C。
第五题
一副扑克54张，平均分成三份，两张王在同一个人手中的概率是多大?
又是概率题，54张牌分成3份，每份18张。
2张王所有的组合有C_{54}^2 = frac {54 * 53} {2} = 1431 ，假设2张王在同一份牌内，一共有C_{18} ^ 2=153 种，由于一共有3份，所以再乘上3，最后的答案就是：
故选B
第六题
以下任务中，正则表达式无法做到的是
常识题，考察对于正则表达式的理解。
显然可以排除AC，这都是正则表达式的基本操作，所以剩下的就是判断B是否正确。正则表达式可以判断模式串的匹配，但无法判断括号是否成对的情况。因为括号成对可能会比较复杂，无法直接通过模式来进行判断。
故选B。
第七题
任何一个二叉树中，如果结点a有左孩子b/右孩子c，则在结点的先序序列、中序序列、后序序列中，（）
考察的是二叉树的遍历，二叉树遍历的三种顺序，左右中指的都是根节点和孩子节点之间的关系，更准确地说就是根节点的遍历顺序。先遍历根，再遍历左右是先序，先遍历左侧再遍历根最后遍历右侧是中序，先遍历左右最后遍历根是后序。
不论什么顺序，可以确定的是左侧一定先于右侧遍历，所以选C。
第八题
计算变量 [0,0,1,1,1,1] 的信息熵
这题有点坑，题目当中有错误。
应该选C，因为信息熵的公式就是sum -p log p ，但题目中的C选项把frac 2 6 打成了frac 2 5
……
看来牛客网审核做得不仔细呀……
第九题
线性表与链表的区别不包括
我们单纯比较数组和链表就行，很明显，对于顺序读取来说，数组和链表都是O(1)，所以是一样的，答案选B。
不知道大家啥感觉，老梁做完之后的感觉是这套笔试题真不是乱出的，绝对是有备而来……
尤其是里面的数学题还是很有难度的，很多老梁都苦思冥想了很久。感谢大家的阅读，希望能有点帮助~
