題目描述：【Math】470. Implement Rand10() Using Rand7()

解題思路：

這道題是用等概率的 Rand7()（[1, 7]）產(chǎn)生等概率的 Rand10()（[1, 10]）畏鼓。

因?yàn)槭且a(chǎn)生等概率的 Rand10()， 因此諸如 Rand7() + Rand7() // 2 的做法就不用想了（不是等概率）壶谒。

但是有一條重要的數(shù)學(xué)性質(zhì)：調(diào)用兩次等概率的 RandN() 可以產(chǎn)生等概率的 Rand(N^2)()云矫，如調(diào)用兩次等概率的 Rand7() 可以產(chǎn)生等概率的 Rand49()。

這就好辦了汗菜，我們可以用 Rand7() 先產(chǎn)生 Rand49()让禀，得到等概率的 [1, 49]挑社，然后隨機(jī)產(chǎn)生一個(gè)數(shù)字，如果是 [41, 49]巡揍，丟棄了也無(wú)妨痛阻。如果是 [1, 40]，對(duì) 10 取模腮敌，就可以得到等概率的 [1, 10]阱当。

那么，問(wèn)題的關(guān)鍵在于糜工，如何 Rand7() 兩次來(lái)產(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]啤斗，然后對(duì)應(yīng)元素相加即可得到等概率的 [1,49] 了（畫(huà)一個(gè)方陣對(duì)應(yīng)著加一下）表箭。

此解決方案可以推廣到所有 RandN 生成 RandM (N < M) 的場(chǎng)景（如果 N >= M，直接丟棄超過(guò) M 的數(shù)字即可）钮莲。

Python3 實(shí)現(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]

問(wèn)題描述：【Math】478. Generate Random Point in a Circle

解題思路：

這道題給出圓的半徑 r 及圓心坐標(biāo)，隨機(jī)生成一個(gè)在圓內(nèi)或圓上的坐標(biāo)崔拥。

很簡(jiǎn)單极舔，只需要隨機(jī)生成兩個(gè)正負(fù)半徑范圍內(nèi)的浮點(diǎn)數(shù) x、y链瓦，然后判斷是否滿(mǎn)足 x^2 + y^2 <= r^2（= 表示可以在圓上）拆魏，如果不滿(mǎn)足，重新生成兩個(gè)浮點(diǎn)數(shù)慈俯；滿(mǎn)足的話(huà)渤刃，各自加上圓心坐標(biāo)就是最后的結(jié)果。

Python3 實(shí)現(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()

問(wèn)題描述：【Binary Search】497. Random Point in Non-overlapping Rectangles

解題思路：

這道題是給一些不重疊的矩陣贴膘，從這些不重疊的矩陣中隨機(jī)采樣一個(gè)整數(shù)點(diǎn)（采樣點(diǎn)包括矩陣邊界）卖子。

因?yàn)榭赡苡泻芏嗑仃嚕覀冇忠ＷC等概率的選取一個(gè)點(diǎn)刑峡，因此我們可以先計(jì)算出每個(gè)矩陣能采樣多少個(gè)點(diǎn)洋闽，并計(jì)算總采樣點(diǎn)，然后 num = random.randint(1, 總采樣點(diǎn)) 采樣一個(gè)數(shù) num突梦。接下來(lái)诫舅，我們要計(jì)算這個(gè) num 落在了哪一個(gè)矩陣中。這時(shí)我們可以像下面的 Leetcode 528 題一樣宫患，按順序求出矩陣的前綴和刊懈，然后使用二分查找的方法計(jì)算 num 落在了哪一個(gè)矩陣中。最后，我們?cè)傧裣旅娴?Leetcode 519 題一樣俏讹，將 num 映射到二維坐標(biāo)上当宴，返回結(jié)果畜吊。

舉個(gè)例子泽疆，假設(shè)有三個(gè)矩陣 rects = [[2,1,5,3], [1,1,2,2], [1,2,3,4]]，我們?nèi)菀椎挠?jì)算出每個(gè)矩陣可以采樣的點(diǎn)數(shù)分別為 [12,4,9]玲献，總采樣點(diǎn)數(shù)為 12+4+9 = 25殉疼，同時(shí)計(jì)算前綴和 pre_sum = [12,16,25]。我們假設(shè)隨機(jī)了一個(gè) [1, 25] 區(qū)間的數(shù) num = 15捌年，那么根據(jù) pre_sum瓢娜，就可以使用二分查找的方法，得到 15 應(yīng)該位于 rects[1] 這個(gè)矩陣中礼预，并且可以知道 15 是 rects[1] 中的第 3 個(gè)樣本點(diǎn)（15-12=3）眠砾。最后，我們把這第 3 個(gè)樣本點(diǎn)映射到二維坐標(biāo)中托酸，假設(shè)按照從左到右褒颈，從下到上映射，我們將會(huì)得到坐標(biāo) [1, 2]励堡。

Python3 實(shí)現(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ù)前綴和進(jìn)行二分查找谷丸，找到隨機(jī)數(shù)落在哪個(gè)矩陣中（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
        # 找到對(duì)應(yīng)矩陣
        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]应结，便于映射到二維坐標(biāo)上
        # 左下角對(duì)應(yīng)0刨疼，右上角對(duì)應(yīng)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()

問(wèn)題描述：【Array】519. Random Flip Matrix

解題思路：

這道題是說(shuō)給一個(gè) n_rows 行 n_clos 的矩陣揩慕，初始化為 0。如果調(diào)用 flip 函數(shù)時(shí)扮休，隨機(jī)將 0 的位置置為 1迎卤，返回矩陣坐標(biāo)。如果調(diào)用 reset 函數(shù)肛炮，重置矩陣為全 0止吐。

因?yàn)闀r(shí)間消耗比較多的肯定是 random() 的調(diào)用次數(shù)，但是矩陣大小可以為 10000*10000侨糟，且 flip 函數(shù)最多調(diào)用 1000 次碍扔，因此我們可以隨機(jī)多次 random() 函數(shù)，找到非 0 的位置秕重，把它置為 1不同。

因?yàn)橐笳{(diào)用的 random() 次數(shù)最少，因此我們可以通過(guò)調(diào)用一次 random() 來(lái)計(jì)算出矩陣坐標(biāo)（而不用兩次）。例如 n_row = 2二拐，n_cols = 3服鹅，我們隨機(jī)一個(gè) [0, n_rows*n_cols-1] 區(qū)間的數(shù) num，然后使用 i = num // n_cols百新、j = num % n_cols 就可以得到對(duì)應(yīng)矩陣的行列坐標(biāo)（i企软，j）。

因?yàn)檫€要考慮到空間饭望，所以直接開(kāi)一個(gè) n_rows 行 n_clos 的矩陣空間肯定是浪費(fèi)的仗哨，而且在調(diào)用 reset 函數(shù)也是 O(n^2) 的復(fù)雜度，這樣肯定不行铅辞。實(shí)際上厌漂，我們只需要保存那些置為 1 的坐標(biāo)到一個(gè)集合中。在 flip 函數(shù)中斟珊，每次 random() 一個(gè)坐標(biāo)苇倡，判斷其是否在集合中（O(1) 復(fù)雜度），如果在囤踩，說(shuō)明這個(gè)坐標(biāo)之前已經(jīng)被置為 1 了旨椒，那就重新 random() 一個(gè)坐標(biāo)；如果不在高职，說(shuō)明這個(gè)坐標(biāo)之前沒(méi)有被置為 1钩乍，就把當(dāng)前坐標(biāo)加入到集合中，同時(shí)返回該坐標(biāo)怔锌。在 reset 函數(shù)中寥粹，我們也只需要 .clear() 清空這個(gè)集合即可。時(shí)間復(fù)雜度和空間復(fù)雜度都極大地降低埃元。

Python3 實(shí)現(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的那些坐標(biāo)

    def flip(self) -> List[int]:
        while True:
            rand = random.randint(1, self.n_rows*self.n_cols) - 1
            row = rand // self.n_cols  # 根據(jù)隨機(jī)的數(shù)字計(jì)算矩陣行列坐標(biāo)
            col = rand % self.n_cols
            if (row, col) not in self.one:  # 之前沒(méi)有被置為1的坐標(biāo)
                self.one.add((row, col))
                return [row, col]

    def reset(self) -> None:
        self.one.clear()  # 清空置為1的那些坐標(biāo)


# 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í)際上是給一個(gè)數(shù)組 w涝涤，其中 w[i] 代表位置 i 的權(quán)重。寫(xiě)一個(gè)函數(shù)岛杀，可以隨機(jī)地獲取位置 i阔拳，選取位置 i 的概率與 w[i] 成正比。

舉個(gè)例子类嗤，w = [1,3,2,2]糊肠，我們需要隨機(jī)的獲取位置 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。

弄懂題意后搔预，我們可以想到先隨機(jī)一個(gè) [1, 8] 中間的數(shù)霹期，比如 7，那么 7 是哪個(gè)位置的呢拯田？很明顯屬于位置 3历造；如果隨機(jī)的數(shù)是 3，則屬于位置 1勿锅。

因此帕膜，我們可以先求出 w = [1,3,2,2] 的前綴和，得到 pre_sum = [1,4,6,8]溢十，分別對(duì)應(yīng)位置 0 到 3，然后隨機(jī)產(chǎn)生一個(gè) num = random.randint(1, 8)（1 <= num <= 8）达吞，使用二分查找的方法確定落在哪個(gè)對(duì)應(yīng)的位置即可张弛。時(shí)間復(fù)雜度為 O(logn)。

Python3 實(shí)現(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)  # 隨機(jī)產(chǎn)生一個(gè)數(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  # 最終的對(duì)應(yīng)位置
        

# Your Solution object will be instantiated and called as such:
# obj = Solution(w)
# param_1 = obj.pickIndex()