Medium

题目描述

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

注意：

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

示例 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 <= xi, yi <= 100
  • 1 <= ri <= min(xi, yi)

解题思路

解题思路

这道题需要统计在至少一个圆内的格点数量。我们可以使用以下方法：

方法一：枚举 + 集合去重（推荐）

  1. 确定搜索范围：首先计算所有圆能覆盖的最小和最大坐标范围，这样可以减少不必要的枚举。

  2. 枚举所有可能的格点：在确定的范围内枚举每个整数坐标点。

  3. 检查点是否在圆内：对于每个格点，检查它是否在至少一个圆内。判断点 (x, y) 是否在圆心 (cx, cy) 半径为 r 的圆内，只需检查：(x - cx)² + (y - cy)² ≤ r²

  4. 使用集合去重：由于同一个格点可能在多个圆内，使用 Set 数据结构自动去重。

优化点：

  • 通过计算所有圆的边界来确定搜索范围，避免枚举过多不必要的点
  • 一旦发现格点在某个圆内，就可以加入结果集，无需继续检查其他圆

时间复杂度主要取决于搜索范围的大小和圆的数量，在给定约束下是可接受的。

代码实现

class Solution {
public:
    int countLatticePoints(vector<vector<int>>& circles) {
        // 确定搜索范围
        int minX = 200, maxX = 0, minY = 200, maxY = 0;
        for (auto& circle : circles) {
            int x = circle[0], y = circle[1], r = circle[2];
            minX = min(minX, x - r);
            maxX = max(maxX, x + r);
            minY = min(minY, y - r);
            maxY = max(maxY, y + r);
        }
        
        set<pair<int, int>> latticePoints;
        
        // 枚举所有可能的格点
        for (int x = minX; x <= maxX; x++) {
            for (int y = minY; y <= maxY; y++) {
                // 检查点(x, y)是否在至少一个圆内
                for (auto& circle : circles) {
                    int cx = circle[0], cy = circle[1], r = circle[2];
                    if ((x - cx) * (x - cx) + (y - cy) * (y - cy) <= r * r) {
                        latticePoints.insert({x, y});
                        break;  // 找到一个包含该点的圆就足够了
                    }
                }
            }
        }
        
        return latticePoints.size();
    }
};

class Solution:
    def countLatticePoints(self, circles: List[List[int]]) -> int:
        # 确定搜索范围
        min_x = min(x - r for x, y, r in circles)
        max_x = max(x + r for x, y, r in circles)
        min_y = min(y - r for x, y, r in circles)
        max_y = max(y + r for x, y, r in circles)
        
        lattice_points = set()
        
        # 枚举所有可能的格点
        for x in range(min_x, max_x + 1):
            for y in range(min_y, max_y + 1):
                # 检查点(x, y)是否在至少一个圆内
                for cx, cy, r in circles:
                    if (x - cx) ** 2 + (y - cy) ** 2 <= r ** 2:
                        lattice_points.add((x, y))
                        break  # 找到一个包含该点的圆就足够了
        
        return len(lattice_points)

public class Solution {
    public int CountLatticePoints(int[][] circles) {
        // 确定搜索范围
        int minX = 200, maxX = 0, minY = 200, maxY = 0;
        foreach (var circle in circles) {
            int x = circle[0], y = circle[1], r = circle[2];
            minX = Math.Min(minX, x - r);
            maxX = Math.Max(maxX, x + r);
            minY = Math.Min(minY, y - r);
            maxY = Math.Max(maxY, y + r);
        }
        
        var latticePoints = new HashSet<(int, int)>();
        
        // 枚举所有可能的格点
        for (int x = minX; x <= maxX; x++) {
            for (int y = minY; y <= maxY; y++) {
                // 检查点(x, y)是否在至少一个圆内
                foreach (var circle in circles) {
                    int cx = circle[0], cy = circle[1], r = circle[2];
                    if ((x - cx) * (x - cx) + (y - cy) * (y - cy) <= r * r) {
                        latticePoints.Add((x, y));
                        break;  // 找到一个包含该点的圆就足够了
                    }
                }
            }
        }
        
        return latticePoints.Count;
    }
}

var countLatticePoints = function(circles) {
    // 确定搜索范围
    let minX = Math.min(...circles.map(([x, y, r]) => x - r));
    let maxX = Math.max(...circles.map(([x, y, r]) => x + r));
    let minY = Math.min(...circles.map(([x, y, r]) => y - r));
    let maxY = Math.max(...circles.map(([x, y, r]) => y + r));
    
    const latticePoints = new Set();
    
    // 枚举所有可能的格点
    for (let x = minX; x <= maxX; x++) {
        for (let y = minY; y <= maxY; y++) {
            // 检查点(x, y)是否在至少一个圆内
            for (const [cx, cy, r] of circles) {
                if ((x - cx) * (x - cx) + (y - cy) * (y - cy) <= r * r) {
                    latticePoints.add(`${x},${y}`);
                    break;  // 找到一个包含该点的圆就足够了
                }
            }
        }
    }
    
    return latticePoints.size;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(W × H × N)，其中 W 和 H 分别是搜索范围的宽度和高度，N 是圆的数量。在最坏情况下，W 和 H 约为 200，N 最大为 200
空间复杂度O(W × H)，用于存储去重后的格点坐标，最坏情况下所有格点都在某个圆内

相关题目