problem0497

README

497. Random Point in Non-overlapping Rectangles

题目

Given a list of non-overlapping axis-aligned rectangles rects, write a function pick which randomly and uniformily picks an integer point in the spacecovered by the rectangles.

Note:

1. An integer pointis a point that has integer coordinates.
2. A pointon the perimeterof a rectangle isincluded in the space covered by the rectangles.
3. ith rectangle = rects[i] =[x1,y1,x2,y2], where [x1, y1]are the integer coordinates of the bottom-left corner, and [x2, y2]are the integer coordinates of the top-right corner.
4. length and width of each rectangle does not exceed 2000.
5. 1 <= rects.length<= 100
6. pick return a point as an array of integer coordinates[p_x, p_y]
7. pick is called at most 10000times.

Example 1:

Input:
["Solution","pick","pick","pick"]
[[[[1,1,5,5]]],[],[],[]]
Output:
[null,[4,1],[4,1],[3,3]]

Example 2:

Input:
["Solution","pick","pick","pick","pick","pick"]
[[[[-2,-2,-1,-1],[1,0,3,0]]],[],[],[],[],[]]
Output:
[null,[-1,-2],[2,0],[-2,-1],[3,0],[-2,-2]]

Explanation of Input Syntax:

The input is two lists:the subroutines calledand theirarguments.Solution'sconstructor has one argument, the array of rectangles rects. pickhas no arguments.Argumentsarealways wrapped with a list, even if there aren't any.

解题思路

见程序注释

Documentation

Index

• type Solution
  • func Constructor(rects [][]int) Solution
  • func (s *Solution) Pick() []int

Types

type Solution

type Solution struct {
	// contains filtered or unexported fields
}

Solution object will be instantiated and called as such: obj := Constructor(rects); param_1 := obj.Pick();

func Constructor

func Constructor(rects [][]int) Solution

Constructor 创建 Solution

func (*Solution) Pick

func (s *Solution) Pick() []int

Pick 返回正方形内的点