2249. 统计圆内格点数目

题目

给你一个二维整数数组 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 <= 200
circles[i].length == 3
1 <= xi, yi <= 100
1 <= ri <= min(xi, yi)

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-lattice-points-inside-a-circle
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

将每个圆内的格点存到哈希集合中，方法是遍历圆的外切正方形，判断是否在圆内。最后集合的大小就是答案。集合的元素如果是数组，Set不会对相同点进行去重，那么使用一个矩阵更合适，可能在圆内的格点坐标都在[200,200]以内。见代码一

还可以直接遍历200*200内的点，是否存在于任意一个圆内。

代码

代码一 矩阵代替HashSet

class Solution {
    public int countLatticePoints(int[][] circles) {
        int[][] mat = new int[201][201];
        for (int[] cir : circles) {
            int r = cir[2];
            int x = cir[0];
            int y = cir[1];
            for (int i = x - r; i <= x + r; i++) {
                for (int j = y - r; j <= y + r; j++) {
                    if ((i - x) * (i - x) + (j - y) * (j - y) <= r * r) {
                        mat[i][j] = 1;
                    }
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < 201; i++) {
            for (int j = 0; j < 201; j++) {
                if (mat[i][j] == 1) {
                    ans++;
                }
            }
        }
        return ans;
    }
}

代码二 使用HashSet

class Solution {
    public int countLatticePoints(int[][] circles) {
        // set中不能存int[]，不然每次new的数组不是一个引用，无法去重
        // 创建一个Point类，重写equals和hashCode就可以了
        // 但是实测慢很多
        Set<Point> set = new HashSet<>();
        for (int[] cir : circles) {
            int r = cir[2];
            int x = cir[0];
            int y = cir[1];
            for (int i = x - r; i <= x + r; i++) {
                for (int j = y - r; j <= y + r; j++) {
                    if ((i - x) * (i - x) + (j - y) * (j - y) <= r * r) {
                        set.add(new Point(i, j));
                    }
                }
            }
        }
        return set.size();
    }
    class Point {
        int x = 0;
        int y = 0;
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Point point = (Point) o;
            return x == point.x &&
                    y == point.y;
        }
        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }
    }
}

代码三 HashSet存List

正确的做法原来是将int[]换为List，这样相同的点就不会被认为是不同的了。但就是会慢很多，比代码二还要慢好几倍……

class Solution {
    public int countLatticePoints(int[][] circles) {
        Set<List<Integer>> set = new HashSet<>();
        for (int[] cir : circles) {
            int r = cir[2];
            int x = cir[0];
            int y = cir[1];
            for (int i = x - r; i <= x + r; i++) {
                for (int j = y - r; j <= y + r; j++) {
                    if ((i - x) * (i - x) + (j - y) * (j - y) <= r * r) {
                        set.add(List.of(i, j));
                    }
                }
            }
        }
        return set.size();
    }
}