382. 链表随机节点 (蓄水池抽样随机 Random 细致注释~）

题目：给定一个单链表，随机选择链表的一个节点，并返回相应的节点值。保证每个节点被选的概率一样。

思路：蓄水池抽样的套路，关键是理解：if random.randint(1,count) == count: res = cur.val

首先，当只有一个数据1的时候，1被选中的概率是100%，也就是说结果只能是1， res 初值为 1.
然后，当一共有两个数据（1，2）时，1和2被选中的概率都是50%。如果这次抽样抽到了2（概率50%），把res更新为2，否则（即没有抽中2，概率也为50%），res的值保留为1.
当一共有三个数据（1，2，3）时，每个数据被抽中的概率应该都是1/3。如果这次抽样抽到了3（概率为1/3），把res更新为3，否则（没有抽中3的概率为2/3，隐含代表抽中了1或2），res保留原值，即在第二步中得到的1或2（虽然第二步已经在1和2之间做出了选择，且选择的结果在之后的步骤中不可逆，但它保证了1和2曾经有相同的概率出线）.
3+ 以此类推～

398. 随机数索引 (蓄水池抽样随机 Random 细致注释~)

题目：给定一个可能含有重复元素的整数数组，要求随机输出给定的数字的索引。您可以假设给定的数字一定存在于数组中。

思路：因为数组可能含有重复元素，为了等概率选取这个给定的数字，必须全部遍历一次。

首先，遍历数组，获得所有target的下标。
然后，随机输出，分别使用了random的两个函数测试。

478. 在圆内随机生成点 (随机 Random 数学细致注释~)

题目：给定圆的半径和圆心的 x、y 坐标，写一个在圆中产生均匀随机点的函数 randPoint 。

思路：本题的标签是“拒绝采样”，意在考察拒绝采样的方法，例如，从正方形中随机取点，然后拒绝圆外的点。

不过，圆本来就有简洁的公式可以直接取得目标范围内的点啊...不用拒绝啦~
随机取得半径(radius * sqrt(random.random()))和弧度(2 * math.pi * random.random())的值，再计算出点的坐标。

470. 用 Rand7() 实现 Rand10() （随机 Random 三类方法细致注释~）

题目：已有方法 rand7 可生成 1 到 7 范围内的均匀随机整数，试写一个方法 rand10 生成 1 到 10 范围内的均匀随机整数。

思路：
方法1：直接使用random多快啊...不过，这是违规的...
方法1.1 return random.randint(1, 10) # 执行用时: 256 ms/ 内存消耗: 17.2 MB
方法1.2 return random.choice(rand7() * 7 + [8, 9, 10]) # 执行用时: 300 ms/ 内存消耗: 17.2 MB

方法2：小学奥数~~ 执行用时: 368 ms/内存消耗: 17.3 MB
使用7个符号等概率映射出十个数字，需要抛开1-7就是7个数字的想法~
取两次，m取1-5，直接作为数值1-5。n取1-6，按照奇偶性决定为m加0还是加5

方法3：套路（7进制）
方法3.1 两位 执行用时: 432 ms/ 内存消耗: 17.3 MB
使用7个数字表达出更多个数字，构造两位7进制，(rand7() - 1) * 7 + rand7() - 1，可以取得0-48之间的数字。

如得到0-39之间的数字，使用（num % 10 + 1）等概率映射出1-10.
如得到40-48之间的数字，重新选择...直到选择到0-39之间的数字。

方法3.2 三位 执行用时: 392 ms/ 内存消耗: 17.2 MB
使用7个数字表达出更多个数字，构造三位7进制，(rand7() - 1) * 49 +(rand7() - 1) * 7 + rand7() - 1，可以取得0-342之间的数字。

如得到0-339之间的数字，使用（num % 10 + 1）等概率映射出1-10.
如得到340-342之间的数字，重新选择...直到选择到0-339之间的数字。

使用两位7进制数字，需在48个数字中拒绝9个，即9/48的拒绝比例。使用三位7进制数字，仅需在342个数字中拒绝3个，即3/342(1/114)的拒绝比例，每次取数需调用rand7()三次并计算，结果显示测试时间为392 ms，优于使用两位7进制。

官网还有进一步的优化算法，思路都是最大化的利用得到的数字，尽量减少调用rand7()以及计算的次数。

528. 按权重随机选择（随机 Random 二分查找细致注释~）

题目：给定一个正整数数组 w ，其中 w[i] 代表下标 i 的权重（下标从 0 开始），请写一个函数 pickIndex ，它可以随机地获取下标 i，选取下标 i 的概率与 w[i] 成正比。

思路：因为选取下标i的概率与w[i]成正比，先计算出w[i]的和，即所有i的权重之和，再在这个权重和的范围内随机取值。然后根据取得的数值确定其对应的i的位置。

更新w数组，用于存储累计和，即截至当前数字累计的权重。原地更新w (不新建数组) 以节省空间。
在“权重之和”（即w[-1])内随机获取数字target。
因为w存储的是截至当前数字累计的权重，查找到target应插入的位置，就可以确认这个元素原来所在的位置。

497. 非重叠矩形中的随机点（随机 Random 二分查找细致注释~）

题目：给定一个非重叠轴对齐矩形的列表 rects，写一个函数 pick 随机均匀地选取矩形覆盖的空间中的整数点。

思路：与528题类似，部分细节不同，参见注释~

710. 黑名单中的随机数（随机 Random 哈希细致注释~）

题目：给定一个包含 [0，n) 中不重复整数的黑名单 blacklist ，写一个函数从 [0, n) 中返回一个不在 blacklist 中的随机整数。

思路：共有N个数字，其中黑名单上有len(blacklist)个数字, 白名单上有N-len(blacklist)个数字. 为了可以使用random.randint(0, self.white_len - 1)随机取得white_len个白名单数字中的一个，使用映射关系处理前white_len个位置中不属于白名单中的数字. 细节参见注释~

519. 随机翻转矩阵 (随机 Random 一次v.s.多次/拒绝抽样细致注释~)

题目：题中给出一个 n_rows 行 n_cols 列的二维矩阵，且所有值被初始化为 0。要求编写一个 flip 函数，均匀随机的将矩阵中的 0 变为 1，并返回该值的位置下标 [row_id,col_id]；同样编写一个 reset 函数，将所有的值都重新置为 0。尽量最少调用随机函数 Math.random()，并且优化时间和空间复杂度。

思路：
方法1：拒绝采样/多次抽样执行用时: 60 ms(99%)/ 内存消耗: 15.4 MB(30%)
随机选取数字作为一维数组的索引位置，使用集合记录翻转过的元素位置，如新选择的位置已经处理过，继续选数。

方法2：一次采样执行用时: 60ms(99%)/ 内存消耗: 15.5 MB(15%)
方法同710。

比较下来，虽然方法2仅抽样一次，但为了实现仅需抽一次，增加了各种操作，时空复杂度和方法1差不多。