统计圆内格点数目
难度:
标签:
题目描述
给你一个二维整数数组 circles ，其中 circles[i] = [xi, yi, ri] 表示网格上圆心为 (xi, yi) 且半径为 ri 的第 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 <= 200circles[i].length == 31 <= xi, yi <= 1001 <= ri <= min(xi, yi)
代码结果
运行时间: 53 ms, 内存: 16.4 MB
/*
* 思路：
* 1. 使用流的方式遍历每个圆，检查圆内的每个整数坐标点。
* 2. 使用集合记录所有出现在至少一个圆内的格点。
* 3. 返回集合的大小。
*/
import java.util.HashSet;
import java.util.Set;
import java.util.stream.IntStream;
public class Solution {
public int countLatticePoints(int[][] circles) {
Set<String> points = new HashSet<>();
IntStream.range(0, circles.length).forEach(index -> {
int x = circles[index][0];
int y = circles[index][1];
int r = circles[index][2];
IntStream.rangeClosed(x - r, x + r).forEach(i -> {
IntStream.rangeClosed(y - r, y + r).forEach(j -> {
if ((i - x) * (i - x) + (j - y) * (j - y) <= r * r) {
points.add(i + "," + j);
}
});
});
});
return points.size();
}
}解释
方法:
此题解采用了差分数组和积分图的思想来计算网格中的格点数。首先，确定一个足够大的矩形区域来包含所有的圆。然后，对于每个圆，计算其横跨的所有行，并在每行的起始和结束位置进行标记，使用差分的方法记录进入圆和离开圆的点。最后，通过累积这些差分值来确定每个点是否在至少一个圆内，进而统计总的格点数目。
时间复杂度:
O(n * r + X * Y)
空间复杂度:
O(X * Y)
代码细节讲解
🦆
在题解中提到使用差分数组和积分图的方法，这个方法与传统的遍历所有网格点相比有什么优势？
▷🦆
如何确定题解中提到的'足够大的矩形区域'的具体大小，以确保包含所有的圆？
▷🦆
题解中计算差分数组时，使用了`isqrt(cr * cr - (y - cy) ** 2)`来确定圆在某一行的横跨范围。此公式的正确性及其如何工作能否详细解释一下？
▷🦆
在计算差分数组时，为什么在圆的右边界的下一个位置`cx + z + 1`处减1？
▷