错排问题:年会抽奖

所谓错排问题就是N个1~N数字的序列都恰好不在对应位上,比如序列3 1 2

题目:年会抽奖

今年公司年会的奖品特别给力,但获奖的规矩却很奇葩:

  1. 首先,所有人员都将一张写有自己名字的字条放入抽奖箱中;
  2. 待所有字条加入完毕,每人从箱中取一个字条;
  3. 如果抽到的字条上写的就是自己的名字,那么“恭喜你,中奖了!”
    现在告诉你参加晚会的人数,请你计算有多少概率会出现无人获奖?
Read more

202. Happy Number

202. Happy Number

思路:

  1. set查重复数字作为重复数字的抽取方法,循环遍历
  2. 假设该步骤总会找到一个数字环,快慢指针法可以类比到该算法。值得注意的,最后happy number最后形成是的数字1的自环,必定停留在1上。而非 happy number最后形成的环一定没有1。
Read more

168. Excel Sheet Column Title

168. Excel Sheet Column Title

从进制的根源出发可以更彻底的探究算法的本源。26进制的的10进制数值计算如下:
$$
s = 26^3x_3 + 26^2x_2+ 26^1x_1 + 26^0x_0
$$
在该题目条件下,$A-Z$分别代表$1-26$,不符合上述计算公式。一般除数取余法直接除于进制值K,(在本题中$K=26$)即可获取低位$x_i$,但是由于零的缺失,$Z=26$的情况,如下公式,除数取余法失效了。

Read more

382. Linked List Random Node

382. Linked List Random Node

思路:

让我想起来之前来宁大讲座的美国教授的出的抽取车流题目。

我们可以使用蓄水池抽样算法(Reservoir Sampling):

考虑抽取一个样例的情况:我们从头遍历一个List,并以$1/k$的概率把第k个元素保留下来。

可以由归纳法得:

第k-1个元素的保留概率是$1/(k - 1)$,在第K个元素遍历时,第K-1次遍历是被保留的元素在这次被保留的概率是$\frac{1}{k-1} * \frac{k - 1}{k}= \frac{1}{k}$ 。

这就保证了遍历一遍全部数组后,各个元素被抽取的等概率性质。

Read more

172. Factorial Trailing Zeroes

思路:

通过判断1 ~n所有数字因子5的个数判断尾零的数量。快速判断方法是:整除 5, 25, 125等等5的倍数的数字其商就是5的倍数的因子数量。

Read more