首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Leetcode【470、478、497、519、528】

Leetcode【470、478、497、519、528】

作者头像
echobingo
发布2019-07-03 11:30:51
8340
发布2019-07-03 11:30:51
举报
题目描述:【Math】470. Implement Rand10() Using Rand7()
解题思路:

这道题是用等概率的 Rand7()([1, 7])产生等概率的 Rand10()([1, 10])。

因为是要产生等概率的 Rand10(), 因此诸如 Rand7() + Rand7() // 2 的做法就不用想了(不是等概率)。

但是有一条重要的数学性质:调用两次等概率的 RandN() 可以产生等概率的 Rand(N^2)(),如调用两次等概率的 Rand7() 可以产生等概率的 Rand49()。

这就好办了,我们可以用 Rand7() 先产生 Rand49(),得到等概率的 [1, 49],然后随机产生一个数字,如果是 [41, 49],丢弃了也无妨。如果是 [1, 40],对 10 取模,就可以得到等概率的 [1, 10]。

那么,问题的关键在于,如何 Rand7() 两次来产生 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 的数字即可)。

Python3 实现:
# 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))  # 构造均匀分布 1~49
            if tem <= 40:  # 丢弃大于40的数字,保证等概率
                return (tem - 1) % 10 + 1  # mod10 可以得到均匀分布的[1,10]
问题描述:【Math】478. Generate Random Point in a Circle
解题思路:

这道题给出圆的半径 r 及圆心坐标,随机生成一个在圆内或圆上的坐标。

很简单,只需要随机生成两个正负半径范围内的浮点数 x、y,然后判断是否满足 x^2 + y^2 <= r^2(= 表示可以在圆上),如果不满足,重新生成两个浮点数;满足的话,各自加上圆心坐标就是最后的结果。

Python3 实现:
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
解题思路:

这道题是给一些不重叠的矩阵,从这些不重叠的矩阵中随机采样一个整数点(采样点包括矩阵边界)。

因为可能有很多矩阵,而我们又要保证等概率的选取一个点,因此我们可以先计算出每个矩阵能采样多少个点,并计算总采样点,然后 num = random.randint(1, 总采样点) 采样一个数 num。接下来,我们要计算这个 num 落在了哪一个矩阵中。这时我们可以像下面的 Leetcode 528 题一样,按顺序求出矩阵的前缀和,然后使用二分查找的方法计算 num 落在了哪一个矩阵中。最后,我们再像下面的 Leetcode 519 题一样,将 num 映射到二维坐标上,返回结果。

举个例子,假设有三个矩阵 rects = [[2,1,5,3], [1,1,2,2], [1,2,3,4]],我们容易的计算出每个矩阵可以采样的点数分别为 [12,4,9],总采样点数为 12+4+9 = 25,同时计算前缀和 pre_sum = [12,16,25]。我们假设随机了一个 [1, 25] 区间的数 num = 15,那么根据 pre_sum,就可以使用二分查找的方法,得到 15 应该位于 rects[1] 这个矩阵中,并且可以知道 15 是 rects[1] 中的第 3 个样本点(15-12=3)。最后,我们把这第 3 个样本点映射到二维坐标中,假设按照从左到右,从下到上映射,我们将会得到坐标 [1, 2]。

Python3 实现:
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
        # 根据前缀和进行二分查找,找到随机数落在哪个矩阵中(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值范围变为[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。如果调用 flip 函数时,随机将 0 的位置置为 1,返回矩阵坐标。如果调用 reset 函数,重置矩阵为全 0。

因为时间消耗比较多的肯定是 random() 的调用次数,但是矩阵大小可以为 10000*10000,且 flip 函数最多调用 1000 次,因此我们可以随机多次 random() 函数,找到非 0 的位置,把它置为 1。

因为要求调用的 random() 次数最少,因此我们可以通过调用一次 random() 来计算出矩阵坐标(而不用两次)。例如 n_row = 2,n_cols = 3,我们随机一个 [0, n_rows*n_cols-1] 区间的数 num,然后使用 i = num // n_colsj = num % n_cols 就可以得到对应矩阵的行列坐标(i,j)。

因为还要考虑到空间,所以直接开一个 n_rows 行 n_clos 的矩阵空间肯定是浪费的,而且在调用 reset 函数也是 O(n^2) 的复杂度,这样肯定不行。实际上,我们只需要保存那些置为 1 的坐标到一个集合中。在 flip 函数中,每次 random() 一个坐标,判断其是否在集合中(O(1) 复杂度),如果在,说明这个坐标之前已经被置为 1 了,那就重新 random() 一个坐标;如果不在,说明这个坐标之前没有被置为 1,就把当前坐标加入到集合中,同时返回该坐标。在 reset 函数中,我们也只需要 .clear() 清空这个集合即可。时间复杂度和空间复杂度都极大地降低。

Python3 实现:
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  # 根据随机的数字计算矩阵行列坐标
            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
解题思路:

这道题实际上是给一个数组 w,其中 w[i] 代表位置 i 的权重。写一个函数,可以随机地获取位置 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] 中间的数,比如 7,那么 7 是哪个位置的呢?很明显属于位置 3;如果随机的数是 3,则属于位置 1。

因此,我们可以先求出 w = [1,3,2,2] 的前缀和,得到 pre_sum = [1,4,6,8],分别对应位置 0 到 3,然后随机产生一个 num = random.randint(1, 8)(1 <= num <= 8),使用二分查找的方法确定落在哪个对应的位置即可。时间复杂度为 O(logn)。

Python3 实现:
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)  # 随机产生一个数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()
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2019.07.01 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目描述:【Math】470. Implement Rand10() Using Rand7()
  • 解题思路:
  • Python3 实现:
  • 问题描述:【Math】478. Generate Random Point in a Circle
  • 解题思路:
  • Python3 实现:
  • 问题描述:【Binary Search】497. Random Point in Non-overlapping Rectangles
  • 解题思路:
  • Python3 实现:
  • 问题描述:【Array】519. Random Flip Matrix
  • 解题思路:
  • Python3 实现:
  • 题目描述:【Binary Search】528. Random Pick with Weight
  • 解题思路:
  • Python3 实现:
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档