统计圆内格点数目

说在前面

🎈每天进行一道算法题目练习，今天的题目是“统计圆内格点数目”。

问题描述

给你一个二维整数数组 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)

思路分析

读完题目之后，我们可以知道，题目会给出一个数组，其中包含了多个圆的信息，圆的表示方式为[圆心横坐标,圆心纵坐标,圆半径],现在是需要我们求出有多少个整数点对会落在圆中。

• 圆的方程

首先我们应该先回忆一下圆的方程，(x-a)²+(y-b)²=r²所表示的曲线是以O（a，b)为圆心，以r为半径的圆，所以要判断坐标是否在圆中，我们只需要将坐标代入a,b，当(x-a)²+(y-b)²<=r²时这说明该坐标在圆上。

• 遍历区域中所有的整数对

在提示中我们可以知道，圆心的坐标为1 <= xi, yi <= 100,而且半径的长度1 <= ri <= min(xi, yi),所以这个区域的范围应该是从0~100

AC代码

/**
 * @param {number[][]} circles
 * @return {number}
 */
var countLatticePoints = function (circles) {
    // 遍历坐标系中的所有点，根据圆的方程过滤出落在圆上面的点
    let res = 0;
    for (let i = 0; i <= 200; i++) {
        for (let j = 0; j <= 200; j++) {
            for (let k = 0; k < circles.length; k++) {
                let x = circles[k][0], y = circles[k][1], r = circles[k][2];
                // 圆心为(a,b) 半径为r的圆的方程为(x-a)²+(x-b)²=r²
                if ((i - x) * (i - x) + (j - y) * (j - y) <= r * r) {
                    res++;
                    break;
                }
            }
        }
    }
    return res;
};

说在后面

🎉这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打打羽毛球🏸 ，平时也喜欢写些东西，既为自己记录📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解🙇，写错的地方望指出，定会认真改进😊，在此谢谢大家的支持，我们下文再见🙌。