「每日LeetCode」2022年6月5日

本文最后更新于：2023年3月19日 晚上

  1. 在圆内随机生成点

478. 在圆内随机生成点

给定圆的半径和圆心的位置，实现函数 randPoint ，在圆中产生均匀随机点。
实现 Solution 类:

  • Solution(double radius, double x_center, double y_center) 用圆的半径 radius 和圆心的位置 (x_center, y_center) 初始化对象
  • randPoint() 返回圆内的一个随机点。圆周上的一点被认为在圆内。答案作为数组返回 [x, y] 。

示例 1：
输入: **[“Solution”,”randPoint”,”randPoint”,”randPoint”] [[1.0, 0.0, 0.0], [], [], []] **输出: **[null, [-0.02493, -0.38077], [0.82314, 0.38945], [0.36572, 0.17248]] **解释: Solution solution = new Solution(1.0, 0.0, 0.0); solution.randPoint ();//返回[-0.02493，-0.38077] solution.randPoint ();//返回[0.82314,0.38945] solution.randPoint ();//返回[0.36572,0.17248]

提示：

  • 0 < radius <= 108
  • -107 <= x_center, y_center <= 107
  • randPoint 最多被调用 3 * 104 次

思路

按题意，随机生成外接正方形中的点，判断是否在圆内，是的话重新生成即可。

解答

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * @param {number} radius
 * @param {number} x_center
 * @param {number} y_center
 */
var Solution = function (radius, x_center, y_center) {
  this.radius = radius;
  this.xCenter = x_center;
  this.yCenter = y_center;
  this.x1 = this.xCenter - this.radius;
  this.x2 = this.xCenter + this.radius;
  this.y1 = this.yCenter - this.radius;
  this.y2 = this.yCenter + this.radius;
};

/**
 * @return {number[]}
 */
Solution.prototype.randPoint = function () {
  const inRound = (x, y) => {
    const instance = Math.sqrt(
      (x - this.xCenter) ** 2 + (y - this.yCenter) ** 2
    );
    return instance <= this.radius;
  };

  while (true) {
    const randomX = _.random(this.x1 * 10000, this.x2 * 10000) / 10000;
    const randomY = _.random(this.y1 * 10000, this.y2 * 10000) / 10000;
    if (inRound(randomX, randomY)) {
      return [randomX, randomY];
    }
  }
};

/**
 * Your Solution object will be instantiated and called as such:
 * var obj = new Solution(radius, x_center, y_center)
 * var param_1 = obj.randPoint()
 */