題目描述：【Math】470. Implement Rand10() Using Rand7()
解題思路：
這道題是用等概率的 Rand7()（[1, 7]）產(chǎn)生等概率的 Rand10()（[1, 10]）。
因為是要產(chǎn)生等概率的 Rand10()， 因此諸如 Rand7() + Rand7() // 2 的做法就不用想了（不是等概率）。
但是有一條重要的數(shù)學性質(zhì)：調(diào)用兩次等概率的 RandN() 可以產(chǎn)生等概率的 Rand(N^2)()，如調(diào)用兩次等概率的 Rand7() 可以產(chǎn)生等概率的 Rand49()。
這就好辦了，我們可以用 Rand7() 先產(chǎn)生 Rand49()，得到等概率的 [1, 49]，然后隨機產(chǎn)生一個數(shù)字，如果是 [41, 49]，丟棄了也無妨。如果是 [1, 40]，對 10 取模，就可以得到等概率的 [1, 10]。
那么，問題的關(guān)鍵在于，如何 Rand7() 兩次來產(chǎn)生 Rand49() 呢？公式如下：
- Rand49() = Rand7() + 7 * (Rand7() - 1)
即 Rand7() 得到 [1,2,3,4,5,6,7]，7 * (Rand7() - 1) 得到 [0,7,14,21,28,35,42]，然后對應元素相加即可得到等概率的 [1,49] 了（畫一個方陣對應著加一下）。
此解決方案可以推廣到所有 RandN 生成 RandM (N < M) 的場景（如果 N >= M，直接丟棄超過 M 的數(shù)字即可）。
Python3 實現(xiàn)：
# The rand7() API is already defined for you.
# def rand7():
# @return a random integer in the range 1 to 7
class Solution:
def rand10(self):
"""
:rtype: int
"""
while True:
tem = rand7() + (7 * (rand7() - 1)) # 構(gòu)造均勻分布 1~49
if tem <= 40: # 丟棄大于40的數(shù)字，保證等概率
return (tem - 1) % 10 + 1 # mod10 可以得到均勻分布的[1,10]
問題描述：【Math】478. Generate Random Point in a Circle
解題思路：
這道題給出圓的半徑 r 及圓心坐標，隨機生成一個在圓內(nèi)或圓上的坐標。
很簡單，只需要隨機生成兩個正負半徑范圍內(nèi)的浮點數(shù) x、y，然后判斷是否滿足 x^2 + y^2 <= r^2（= 表示可以在圓上），如果不滿足，重新生成兩個浮點數(shù)；滿足的話，各自加上圓心坐標就是最后的結(jié)果。
Python3 實現(xiàn)：
class Solution:
def __init__(self, radius: float, x_center: float, y_center: float):
self.radius = radius
self.x_center = x_center
self.y_center = y_center
def randPoint(self) -> List[float]:
while True:
x = random.uniform(-self.radius, self.radius)
y = random.uniform(-self.radius, self.radius)
if x * x + y * y <= self.radius * self.radius:
return [self.x_center + x, self.y_center + y]
# Your Solution object will be instantiated and called as such:
# obj = Solution(radius, x_center, y_center)
# param_1 = obj.randPoint()
問題描述：【Binary Search】497. Random Point in Non-overlapping Rectangles
解題思路：
這道題是給一些不重疊的矩陣，從這些不重疊的矩陣中隨機采樣一個整數(shù)點（采樣點包括矩陣邊界）。
因為可能有很多矩陣，而我們又要保證等概率的選取一個點，因此我們可以先計算出每個矩陣能采樣多少個點，并計算總采樣點，然后 num = random.randint(1, 總采樣點) 采樣一個數(shù) num。接下來，我們要計算這個 num 落在了哪一個矩陣中。這時我們可以像下面的 Leetcode 528 題一樣，按順序求出矩陣的前綴和，然后使用二分查找的方法計算 num 落在了哪一個矩陣中。最后，我們再像下面的 Leetcode 519 題一樣，將 num 映射到二維坐標上，返回結(jié)果。
舉個例子，假設有三個矩陣 rects = [[2,1,5,3], [1,1,2,2], [1,2,3,4]]，我們?nèi)菀椎挠嬎愠雒總€矩陣可以采樣的點數(shù)分別為 [12,4,9]，總采樣點數(shù)為 12+4+9 = 25，同時計算前綴和 pre_sum = [12,16,25]。我們假設隨機了一個 [1, 25] 區(qū)間的數(shù) num = 15，那么根據(jù) pre_sum，就可以使用二分查找的方法，得到 15 應該位于 rects[1] 這個矩陣中，并且可以知道 15 是 rects[1] 中的第 3 個樣本點（15-12=3）。最后，我們把這第 3 個樣本點映射到二維坐標中，假設按照從左到右，從下到上映射，我們將會得到坐標 [1, 2]。
Python3 實現(xiàn)：
class Solution:
def __init__(self, rects: List[List[int]]):
self.rects = rects
self.pre_sum = [0] * len(rects) # 前綴和
self.pre_sum[0] = (rects[0][2] - rects[0][0] + 1) * (rects[0][3] - rects[0][1] + 1)
for i in range(1, len(rects)):
self.pre_sum[i] = self.pre_sum[i-1] + (rects[i][2] - rects[i][0] + 1) * (rects[i][3] - rects[i][1] + 1)
def pick(self) -> List[int]:
rand = random.randint(1, self.pre_sum[-1])
low, high = 0, len(self.pre_sum) - 1
# 根據(jù)前綴和進行二分查找，找到隨機數(shù)落在哪個矩陣中（low即為位置）
while low <= high:
mid = (low + high) // 2
if self.pre_sum[mid] < rand:
low = mid + 1
elif self.pre_sum[mid] >= rand:
high = mid - 1
# 找到對應矩陣
x1, y1, x2, y2 = self.rects[low][0], self.rects[low][1], self.rects[low][2], self.rects[low][3]
rows = x2 - x1 + 1
cols = y2 - y1 + 1
if low != 0: # 在該矩陣中的rand值，取值為[1, rows*cols]
rand -= self.pre_sum[low-1]
rand -= 1 # 將rand值范圍變?yōu)閇0, rows*cols-1]，便于映射到二維坐標上
# 左下角對應0，右上角對應rows*cols-1，從左到右，從下到上
i = x1 + rand % rows
j = y1 + rand // rows
return [i, j]
# Your Solution object will be instantiated and called as such:
# obj = Solution(rects)
# param_1 = obj.pick()
問題描述：【Array】519. Random Flip Matrix
解題思路：
這道題是說給一個 n_rows 行 n_clos 的矩陣，初始化為 0。如果調(diào)用 flip 函數(shù)時，隨機將 0 的位置置為 1，返回矩陣坐標。如果調(diào)用 reset 函數(shù)，重置矩陣為全 0。
因為時間消耗比較多的肯定是 random() 的調(diào)用次數(shù)，但是矩陣大小可以為 10000*10000，且 flip 函數(shù)最多調(diào)用 1000 次，因此我們可以隨機多次 random() 函數(shù)，找到非 0 的位置，把它置為 1。
因為要求調(diào)用的 random() 次數(shù)最少，因此我們可以通過調(diào)用一次 random() 來計算出矩陣坐標（而不用兩次）。例如 n_row = 2，n_cols = 3，我們隨機一個 [0, n_rows*n_cols-1] 區(qū)間的數(shù) num，然后使用 i = num // n_cols、j = num % n_cols 就可以得到對應矩陣的行列坐標（i，j）。
因為還要考慮到空間，所以直接開一個 n_rows 行 n_clos 的矩陣空間肯定是浪費的，而且在調(diào)用 reset 函數(shù)也是 O(n^2) 的復雜度，這樣肯定不行。實際上，我們只需要保存那些置為 1 的坐標到一個集合中。在 flip 函數(shù)中，每次 random() 一個坐標，判斷其是否在集合中（O(1) 復雜度），如果在，說明這個坐標之前已經(jīng)被置為 1 了，那就重新 random() 一個坐標；如果不在，說明這個坐標之前沒有被置為 1，就把當前坐標加入到集合中，同時返回該坐標。在 reset 函數(shù)中，我們也只需要 .clear() 清空這個集合即可。時間復雜度和空間復雜度都極大地降低。
Python3 實現(xiàn)：
class Solution:
def __init__(self, n_rows: int, n_cols: int):
self.n_rows = n_rows
self.n_cols = n_cols
self.one = set() # 保存置為1的那些坐標
def flip(self) -> List[int]:
while True:
rand = random.randint(1, self.n_rows*self.n_cols) - 1
row = rand // self.n_cols # 根據(jù)隨機的數(shù)字計算矩陣行列坐標
col = rand % self.n_cols
if (row, col) not in self.one: # 之前沒有被置為1的坐標
self.one.add((row, col))
return [row, col]
def reset(self) -> None:
self.one.clear() # 清空置為1的那些坐標
# Your Solution object will be instantiated and called as such:
# obj = Solution(n_rows, n_cols)
# param_1 = obj.flip()
# obj.reset()
題目描述：【Binary Search】528. Random Pick with Weight
解題思路：
這道題實際上是給一個數(shù)組 w，其中 w[i] 代表位置 i 的權(quán)重。寫一個函數(shù)，可以隨機地獲取位置 i，選取位置 i 的概率與 w[i] 成正比。
舉個例子，w = [1,3,2,2]，我們需要隨機的獲取位置 i (0、1、2、3)，選取位置 0 的概率是 1/(1+3+2+2) = 1/8，選取位置 1 的概率是 3/(1+3+2+2) = 3/8，選取位置 2 的概率是 2/(1+3+2+2) = 2/8，選取位置 3 的概率是 1/(1+3+2+2) = 2/8。
弄懂題意后，我們可以想到先隨機一個 [1, 8] 中間的數(shù)，比如 7，那么 7 是哪個位置的呢？很明顯屬于位置 3；如果隨機的數(shù)是 3，則屬于位置 1。
因此，我們可以先求出 w = [1,3,2,2] 的前綴和，得到 pre_sum = [1,4,6,8]，分別對應位置 0 到 3，然后隨機產(chǎn)生一個 num = random.randint(1, 8)（1 <= num <= 8），使用二分查找的方法確定落在哪個對應的位置即可。時間復雜度為 O(logn)。
Python3 實現(xiàn)：
class Solution:
def __init__(self, w: List[int]):
self.tot = sum(w) # 總和
self.pre_sum = [0] * len(w) # 前綴和
self.pre_sum[0] = w[0]
for i in range(1, len(w)):
self.pre_sum[i] = self.pre_sum[i-1] + w[i]
def pickIndex(self) -> int:
tot = self.tot
pre_sum = self.pre_sum
rand = random.randint(1, tot) # 隨機產(chǎn)生一個數(shù)1<=rand<=tot
low, high = 0, len(pre_sum) - 1
while low <= high: # 二分查找
mid = (low + high) // 2
if pre_sum[mid] < rand:
low = mid + 1
elif pre_sum[mid] >= rand:
high = mid - 1
return low # 最終的對應位置
# Your Solution object will be instantiated and called as such:
# obj = Solution(w)
# param_1 = obj.pickIndex()
