LeetCode 题解工作台
圆形靶内的最大飞镖数量
Alice 向一面非常大的墙上掷出 n 支飞镖。给你一个数组 darts ，其中 darts[i] = [x i , y i ] 表示 Alice 掷出的第 i 支飞镖落在墙上的位置。 Bob 知道墙上所有 n 支飞镖的位置。他想要往墙上放置一个半径为 r 的圆形靶。使 Alice 掷出的飞镖尽可能…
3
题型
2
代码语言
3
相关题
当前训练重点
困难 · 数组·数学
答案摘要
class Solution: def numPoints(self, darts: list[list[int]], r: int) -> int:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·数学 题型思路
题目描述
Alice 向一面非常大的墙上掷出 n 支飞镖。给你一个数组 darts ，其中 darts[i] = [xi, yi] 表示 Alice 掷出的第 i 支飞镖落在墙上的位置。
Bob 知道墙上所有 n 支飞镖的位置。他想要往墙上放置一个半径为 r 的圆形靶。使 Alice 掷出的飞镖尽可能多地落在靶上。
给你整数 r ，请返回能够落在 任意 半径为 r 的圆形靶内或靶上的最大飞镖数。
示例 1 ：
输入：darts = [[-2,0],[2,0],[0,2],[0,-2]], r = 2 输出：4 解释：如果圆形靶的圆心为 (0,0) ，半径为 2 ，所有的飞镖都落在靶上，此时落在靶上的飞镖数最大，值为 4 。
示例 2 ：
输入：darts = [[-3,0],[3,0],[2,6],[5,4],[0,9],[7,8]], r = 5 输出：5 解释：如果圆形靶的圆心为 (0,4) ，半径为 5 ，则除了 (7,8) 之外的飞镖都落在靶上，此时落在靶上的飞镖数最大，值为 5 。
提示：
1 <= darts.length <= 100darts[i].length == 2-104 <= xi, yi <= 104darts中的元素互不相同1 <= r <= 5000
解题思路
方法一
class Solution:
def numPoints(self, darts: list[list[int]], r: int) -> int:
def countDarts(x, y):
count = 0
for x1, y1 in darts:
if dist((x, y), (x1, y1)) <= r + 1e-7:
count += 1
return count
def possibleCenters(x1, y1, x2, y2):
dx, dy = x2 - x1, y2 - y1
d = sqrt(dx * dx + dy * dy)
if d > 2 * r:
return []
mid_x, mid_y = (x1 + x2) / 2, (y1 + y2) / 2
dist_to_center = sqrt(r * r - (d / 2) * (d / 2))
offset_x = dist_to_center * dy / d
offset_y = dist_to_center * -dx / d
return [
(mid_x + offset_x, mid_y + offset_y),
(mid_x - offset_x, mid_y - offset_y),
]
n = len(darts)
max_darts = 1
for i in range(n):
for j in range(i + 1, n):
centers = possibleCenters(
darts[i][0], darts[i][1], darts[j][0], darts[j][1]
)
for center in centers:
max_darts = max(max_darts, countDarts(center[0], center[1]))
return max_darts
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
The candidate understands how to handle geometric problems efficiently.
- question_mark
The candidate demonstrates familiarity with the Euclidean distance and circle geometry.
- question_mark
The candidate can identify trade-offs between brute-force and optimized approaches in geometry-based problems.
常见陷阱
外企场景- error
Failing to properly compute the distance between two points using the Euclidean formula.
- error
Not recognizing that the dartboard can be moved to optimize dart inclusion.
- error
Not optimizing the solution by reusing computations for the same dartboard placement.
进阶变体
外企场景- arrow_right_alt
What if the dartboard had a different shape, such as an ellipse instead of a circle?
- arrow_right_alt
What if we were asked to maximize darts inside multiple dartboards of fixed size?
- arrow_right_alt
How would the solution change if dartboard placement was restricted to certain regions of the wall?