What is the pattern used in 'Count Lattice Points Inside a Circle'?

The primary pattern involves array scanning plus hash lookup to count unique lattice points inside any given circle.

How do I ensure lattice points are only counted once?

Use a hash set to store unique points and add points only if they are not already in the set.

Can I optimize the range of points I check for each circle?

Yes, you can reduce unnecessary checks by focusing on areas where the lattice points may lie inside the given circles.

How do I check if a point is inside a circle?

For a point (x, y) to be inside a circle with center (xi, yi) and radius ri, the condition (x - xi)^2 + (y - yi)^2 <= ri^2 must hold.

How does GhostInterview help with this problem?

GhostInterview assists by providing optimized solution strategies, including efficient array scanning, hash lookups, and guidance on managing geometric constraints.

#2249

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

统计圆内格点数目

给你一个二维整数数组 circles ，其中 circles[i] = [x i , y i , r i ] 表示网格上圆心为 (x i , y i ) 且半径为 r i 的第 i 个圆，返回出现在至少一个圆内的格点数目。注意：格点是指整数坐标对应的点。圆周上的点也被视为出现在圆内…

数组哈希表数学几何枚举

题目描述

给你一个二维整数数组 circles ，其中 circles[i] = [x_i, y_i, r_i] 表示网格上圆心为 (x_i, y_i) 且半径为 r_i 的第 i 个圆，返回出现在 至少一个 圆内的 格点数目 。

注意：

格点是指整数坐标对应的点。
圆周上的点 也被视为出现在圆内的点。

示例 1：

输入：circles = [[2,2,1]]
输出：5
解释：
给定的圆如上图所示。
出现在圆内的格点为 (1, 2)、(2, 1)、(2, 2)、(2, 3) 和 (3, 2)，在图中用绿色标识。
像 (1, 1) 和 (1, 3) 这样用红色标识的点，并未出现在圆内。
因此，出现在至少一个圆内的格点数目是 5 。

示例 2：

输入：circles = [[2,2,2],[3,4,1]]
输出：16
解释：
给定的圆如上图所示。
共有 16 个格点出现在至少一个圆内。
其中部分点的坐标是 (0, 2)、(2, 0)、(2, 4)、(3, 2) 和 (4, 4) 。

提示：

1 <= circles.length <= 200
circles[i].length == 3
1 <= x_i, y_i <= 100
1 <= r_i <= min(x_i, y_i)

lightbulb

解题思路

方法一：枚举

枚举所有的格点，判断其是否在圆内，如果在圆内，则答案加一。

枚举的时候，可以将所有圆的最大横纵坐标求出来，作为枚举的上界。

时间复杂度 $O(X \times Y \times n)$ ，空间复杂度 $O(1)$ 。其中 $X$ 和 $Y$ 分别为所有圆的最大横纵坐标，而 $n$ 为圆的个数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def countLatticePoints(self, circles: List[List[int]]) -> int:
        ans = 0
        mx = max(x + r for x, _, r in circles)
        my = max(y + r for _, y, r in circles)
        for i in range(mx + 1):
            for j in range(my + 1):
                for x, y, r in circles:
                    dx, dy = i - x, j - y
                    if dx * dx + dy * dy <= r * r:
                        ans += 1
                        break
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Ability to optimize array scanning and hash lookups.
question_mark
Focus on counting unique lattice points across multiple circles.
question_mark
Understanding of geometric relationships between points and circles.

warning

常见陷阱

外企场景

error
Failing to ensure points inside multiple circles are counted only once.
error
Overlooking the need to check multiple circles for each point.
error
Not optimizing the range of points to check, leading to excessive computation.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Count lattice points inside multiple circles with different sizes.
arrow_right_alt
Consider dynamic radius or center changes for each circle.
arrow_right_alt
Extend the problem to consider other geometric shapes, like ellipses.

help

常见问题

外企场景

继续练习

#3588 找到最大三角形面积 #3025 人员站位的方案数 I #3027 人员站位的方案数 II