算法

优惠券

问题

一个饭店发行一套优惠券，一套里面总共有 n 张不同的优惠券，顾客每次吃一次，可以随机获得一张优惠券。如果收集齐一套，下次吃饭可以打折。请问：顾客要来多少次才能收集齐一套优惠券？（是不是和小时候吃零食收集刮刮卡的情形是一样的，呵呵）

分析

问题的难点在于顾客获得的优惠劵可能会有重复。但是，我们可以换一角度思考。

• 假设顾客第一次来，他一定会得到一张独一无二的优惠券

• 第二次来的时候，得到的优惠券和上次不重复的概率是 (n-1) / n， 那我们期望的天数是 n / (n-1)

• 第三次来的时候，得到与上两次不同的概率是 (n - 2) / n，….

• 到第 n 次来的时候，与前 n - 1 次收集到的优惠券不同的概率是 1 / n。

换句话说，拿到第一张不重复的优惠券需要的次数是 1， 拿到第二张与前一张不同的优惠券需要的次数是 n / (n - 1), 拿到第三张与前两张不同的优惠劵需要的次数是 n /(n - 2), 以此类推，拿到最后一张不重复的优惠券所需要的次数是 n / 1.

答案

总的次数是 1 + n / (n-1) + n /(n-2) + n / (n -3) + … + n ~= n lg n.

数组中第K个最大元素（leetcode215）& 栈的最小数

求根； 先用牛顿法推了迭代公式写了代码；之后问还有其他做法么？就说了二分法的思路。

手写BN的实现。注意BN的mean和std是在哪个维度求梯度的，mean和std是滑动平均的值。基于numpy实现

二分法，求某个数的位置

一个正整数组成的数组，分成连续的M段，问每段的数之和的最大值最小是多少？

例如：a=[10,6,2,7,3],M=2,答案为16，两段分为[10,6][2,7,3]。

1

一段字符串的句子，由多个单词组成，返回颠倒后的句子（单词不颠倒）
两个有序数组，返回并集的中位数