Table of Content
题目如下：
这道题的主要解题思路是利用矩形所包含的整数坐标点来生成对于的权重，如下图所示：
对于一个长宽为a，b的矩形，我们可以通过: (a+1)*(b+1)来获取其包含整数点的数量从而生成对应的权重信息。根据权重信息，有两种解法：
解法①：使用random.choices() 根据权重选择矩形，然后生成随机点。 参考代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
''' @auther: Jedi.L @Date: Tue, Feb 26, 2019 12:10 @Blog: www.tundrazone.com @Email: xiangyangan@gmail.com ''' import random class Solution: def __init__(self, rects: List[List[int]]): self.rects = rects self.weights = [] for [x_bl, y_bl, x_tr, y_tr] in self.rects: self.weights.append((x_tr - x_bl + 1) * (y_tr - y_bl + 1)) def pick(self) -> List[int]: [x_bl, y_bl, x_tr, y_tr] = random.choices( self.rects, weights=self.weights)[0] res = [ random.randrange(x_bl, x_tr + 1), random.randrange(y_bl, y_tr + 1) ] return res |
解法②：使用bisect.bisect_left(), 根据权重产生的累积概率选择矩形，再生成随机点。参考代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
''' @auther: Jedi.L @Date: Tue, Feb 26, 2019 12:10 @Blog: www.tundrazone.com @Email: xiangyangan@gmail.com ''' import random import bisect class Solution: def __init__(self, rects): self.rects, self.ranges, point_sum = rects, [], 0 for x_bl, y_bl, x_tr, y_tr in rects: point_sum += (x_tr - x_bl + 1) * (y_tr - y_bl + 1) self.ranges.append(point_sum) def pick(self): x1, y1, x2, y2 = self.rects[bisect.bisect_left( self.ranges, random.randint(1, self.ranges[-1]))] return [random.randint(x1, x2), random.randint(y1, y2)] |
欢迎关注微信公众号“苔原带”
