関小君刷题记

题目大意：

圆形靶内的最大飞镖数量

墙壁上挂着一个圆形的飞镖靶。现在请你蒙着眼睛向靶上投掷飞镖。

投掷到墙上的飞镖用二维平面上的点坐标数组表示。飞镖靶的半径为 r 。

请返回能够落在 任意 半径为 r 的圆形靶内或靶上的最大飞镖数。

示例 1：

输入：points = [[-2,0],[2,0],[0,2],[0,-2]], r = 2
输出：4
解释：如果圆形的飞镖靶的圆心为 (0,0) ，半径为 2 ，所有的飞镖都落在靶上，此时落在靶上的飞镖数最大，值为 4 。

示例 2：

输入：points = [[-3,0],[3,0],[2,6],[5,4],[0,9],[7,8]], r = 5
输出：5
解释：如果圆形的飞镖靶的圆心为 (0,4) ，半径为 5 ，则除了 (7,8) 之外的飞镖都落在靶上，此时落在靶上的飞镖数最大，值为 5 。

示例 3：

输入：points = [[-2,0],[2,0],[0,2],[0,-2]], r = 1
输出：1

示例 4：

输入：points = [[1,2],[3,5],[1,-1],[2,3],[4,1],[1,3]], r = 2
输出：4

提示：

• 1 <= points.length <= 100
• points[i].length == 2
• -10^4 <= points[i][0], points[i][1] <= 10^4
• 1 <= r <= 5000

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1453

解题思路分析：

个人认为这是一道并不适合于在面试中出现的数学题目。周赛时，我并没能在规定时间内提交代码，主要原因是卡在了如何通过2点以及半径求出圆心坐标的方法上（汗!）。

回到本题的解题思路，由于题目的数据规模并不大，因此可以考虑使用暴力枚举的方法。首先我们要明确一个知识点：如果两个点都在圆的边上，那么再通过圆的半径我们可以计算出圆心所在的位置，而圆心的位置可能存在2种可能：

另外，当两点距离等于圆的直径时，圆心坐标是唯一的。反之如果两点间距离大于直径，那么显然这两个点则无法共圆。

明确了上面的理论，我们可以使用2层循环去枚举每两个点间的关系，如果他们间的距离小于等于直径，那么先找到这2个点可以确定的圆心位置。然后再使用一层循环去遍历其他点，看其他点与圆心的距离是否小于等于半径。统计出所有满足条件的点后我们可以得到当前情况下能够共圆的点的个数，并使用该个数更新全局最大个数。循环完所有两点间的关系后，全局最大个数即是返回结果。

实现代码：

public int numPoints(int[][] points, int r) {
    int n = points.length;
    int res = 1;
    for(int i=0; i<n; i++){
        for(int j=i+1; j<n; j++){
            double[] a = new double[]{points[i][0], points[i][1]};
            double[] b = new double[]{points[j][0], points[j][1]};
            double[] center = findCenter(a, b, (double)r);
            if(!Double.isNaN(center[0]) && !Double.isNaN(center[1])){
                int cur = 2;
                for(int k=0; k<n; k++) if(k!=i && k!=j){
                    if(dist(center, new double[]{points[k][0], points[k][1]})<=r){
                        cur++;
                    }
                }
                res = Math.max(res, cur);                    
            }
        }
    }
    return res;
}

public double[] findCenter(double[] a, double[] b, double r) {
    double[] mid = new double[2];
    double[] res = new double[2];
    mid[0]=(a[0]+b[0])/2;
    mid[1]=(a[1]+b[1])/2;
    double angle = Math.atan2(a[0]-b[0],b[1]-a[1]);
    double d = Math.sqrt(r*r-Math.pow(dist(a,mid),2));
    res[0] = mid[0]+d*Math.cos(angle);
    res[1] = mid[1]+d*Math.sin(angle);
    return res;
}

public double dist(double[] a, double[] b){
    return Math.sqrt(Math.pow(a[0]-b[0],2) + Math.pow(a[1]-b[1],2));
}

本题解法执行时间为29ms。

Runtime: 29 ms, faster than 100.00% of Java online submissions for Maximum Number of Darts Inside of a Circular Dartboard.

Memory Usage: 39.3 MB, less than 100.00% of Java online submissions for Maximum Number of Darts Inside of a Circular Dartboard.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1453-maximum-number-of-darts-inside-of-a-circular-dartboard-解题思路分析/