这部分在国庆前完成的，大师国庆这天才释放出来，给自己的假期增加一点工作量。。。

744. Find Smallest Letter Greater Than Target

这道题在面试中见到了，当时回答得可真是渣渣啊。这次结合了循环不变量的思路去做这道题，主要的思想就是搜索区间的循环不变量是想要找的元素一定在区间内。这就使得和正常的二分搜索出现了一些小的区别，当支点等于target时，我还要向右搜索，当支点大于target时，我要向左搜索，但是要把当前支点放在区间内，然后当区间元素个数为两个时可能区间不能在缩小，然后就自左向右顺序搜索区间，返回第一个比target大的元素，如果没有，就返回第一个元素。

然而Solution中给了格外Pythonic的代码：

1
2
3
4

class Solution(object):
    def nextGreatestLetter(self, letters, target):
        index = bisect.bisect(letters, target)
        return letters[index % len(letters)]

Read More

均匀采样

在采样技术中，在$$$[0, 1)$$$区间内进行均匀采样可以说是采样算法的基石，比如说逆变换采样就是针对CDF函数的值域上进行采样，对离散分布的轮盘赌算法同理是一种离散分布的逆变换采样，拒绝采样中判断对于一个采样是否被接受需要均匀采样，等等等等，不一而足。而均匀采样底层可能是基于真随机源，也可能是基于某种伪随机数生成器的。

常见的伪随机数生成器通常是采用线性同余法，比如gcc中的glibc版本，对于python3，是使用os内置包中的urandom返回随机比特转换为浮点数。

1
2
3
4

# Lib/random.py
def random(self):
    """Get the next random number in the range [0.0, 1.0)."""
    return (int.from_bytes(_urandom(7), 'big') >> 3) * RECIP_BPF

其中urandom返回7byte的随机字节，RECIP_BPF的值是$$$\frac{1}{2^{53}}$$$，所以该函数返回一个小数点后有56位的二进制浮点数。

Read More

对于计算机中的数值计算来说，很多情况我们认为简单的运算对于计算机来说可能并没有那么简单。对于计算机体系结构和底层的实现，我了解的非常浅薄，这里只是为了引出Q_rsqrt算法谈谈自己的理解。首先可以知道的是，目前来说，对于加法和移位，计算机可以高效的完成，因为这两种操作对于CPU的计算单元会有高效的硬件实现。对于减法同样可以以和加法差不多的指令周期内完成，因为数值在计算机内以补码形式形式存放，加法和减法的操作具有高度一致性。对于乘法来说，就要比加法慢上很多，因为乘法在计算机内是通过多次移位与相加组合完成的。而除法是最慢的一种基本操作，迭代的次数与惩罚差不多，但是由于额外的判断操作，其需要的指令周期数可能要是乘法的两倍甚至更多。

(引用自果壳网的讨论)：除法一般都是减法和移位的综合体，就像你用竖式算的一样。里面每一位要进行的判断，时间也就用得多。…… 在没有除法指令的CPU上，也是用类似的程式进行，那就慢得更加多了。在某些优化的情况下，除法可以用乘法代替，但还是比乘法慢。 …… 因为很多处理器没有硬件除法单元。就算有硬件除法单元，也比普通运算慢。因为在硬件上除法使用的是类似CORDIC的方法（与开方、三角函数的CORDIC算法很相似，所以一般都一起共用一个单元，称为SFU），为了达到精度一般要迭代几十次的，花费数十个周期很正常。

对于通过组合四则运算与符合运算，可以进行六种基本初等函数的计算，对于幂运算可以使用快速幂算法将其计算复杂度做到O(logn)，类似的斐波那契数列也可以通过引入矩阵乘法，在对数时间复杂度内计算完毕。而对于$$$e^x$$$，常规做法是使用泰勒展开式$$$1+\frac{x}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}+…$$$进行逼近。

Read More

在面试中遇到了这么一道问题：有一个抽奖系统，内存很小（存不下所有用户的id），在截止时间前任何用户都可以访问该系统参与一次抽奖，到了截止时间后要求以等概率的可能性选取一个合法用户作为幸运用户。比如截止时间前有十个用户访问该系统，那么要求每个用户都有 10% 的概率被选中，如果截止时间前有100个用户访问该系统，那么到了截止时间的时候，要求每个用户有 1% 的概率被选中。

由于之前看过《编程珠玑》，所以很快的想到了该问题实际上是蓄水池抽样问题加了一个实际场景。蓄水池问题解决的就是在流数据中进行等概率抽样的问题。先考虑一个简单情况，需要在流数据中等概率的选取一个元素。那么算法思想是，对于第$$$k$$$个元素，有$$$\frac{1}{k}$$$的概率被选中，作为当前的“幸运元素”，当流算法需要抽样时返回当前元素即可。

Read More

一共三十来道题，一道能打的都没有！（傲娇脸）

Read More