【力扣每日一题】——统计圆里格点数量

统计圆里格点数量

一、题目描述

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

注意：

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

示例：

输入：circles = [[2,2,1]]
输出：5
解释：
给定的圆如上图所示。
出现在圆内的格点为 (1, 2)、(2, 1)、(2, 2)、(2, 3) 和 (3, 2)，在图中用绿色标识。
像 (1, 1) 和 (1, 3) 这样用红色标识的点，并未出现在圆内。
因此，出现在至少一个圆内的格点数目是 5 。

提示：

• 1 <= circles.length <= 200
• circles[i].length == 3
• 1 <= xi, yi <= 100
• 1 <= ri <= min(xi, yi)

二、题目分析

这个题思路很简单，因为数据量很小，枚举就可以，但是我看到去重，首先想到的是set集合，然后把点的坐标转化成字符串存入set集合，但是我实现的时候使用的是 x +""+ y，

class Solution {
    public int countLatticePoints(int[][] circles) {

        int n = circles.length;
        Set<String> set = new HashSet<>();

        for(int i = 0; i < n;i++){
            //圆心x坐标
            int x = circles[i][0];
            //圆心y坐标
            int y = circles[i][1];
            //半径
            int r = circles[i][2];
          
            
            for(int j = x-r; j <= x+r;j++){
                for(int k = y -r; k<= y+r;k++){
                    int num =  (j-x ) *(j-x)+ (k-y) *(k-y);
                    if(num <= r*r){
                        //存入set集合
                        set.add(j+" "+k);
                    }
                }
            }

        }
       
        return  set.size();
    }
}

然后就开始了 坐牢时间......

[[10,7,3],[5,9,5],[10,4,2],[3,8,2],[2,3,1],[2,10,1],[10,9,8],[6,6,3],[8,6,3],[9,8,7],[9,4,3],[7,4,1],[4,6,2],[4,3,2],[8,3,3]]

这组样例一直过不了，少一个点，然后就一直在想咋会少个点思路没问题啊

周赛结束后看完大佬的代码

• 直接枚举数据范围所有点，遇到一个点满足题意就跳出循环进行下一个点的判断，这样去重比set高效很多

但是，我还是不明白为啥我写的会少一个点，然后我就在本地测试下，两组代码用list集合存入x +""+ y，然后对集合进行排序输出，终于发现少了一个112

原来这样转字符串 x +""+ y 会造成像(11, 2) 和 （1,12) 最后都是"112" 只需要转成这样的字符串就能解决x +" "+ y，我哭死..........

三、代码实现

class Solution {
    public int countLatticePoints(int[][] circles) {

        int n = circles.length;
        Set<String> set = new HashSet<>();

        for(int i = 0; i < n;i++){
               //圆心x坐标
            int x = circles[i][0];
            //圆心y坐标
            int y = circles[i][1];
            //半径
            int r = circles[i][2];
          
            
            for(int j = x-r; j <= x+r;j++){
                for(int k = y -r; k<= y+r;k++){
                    int num =  (j-x ) *(j-x)+ (k-y) *(k-y);
                    if(num <= r*r){
                        set.add(j+" "+k);
                    }
                }
            }

        }
       
        return  set.size();
    }
}

AC了，但是这运行时间总觉得很高

唉，还是题解区大佬们给的代码好，枚举都比我这代码效率高

class Solution {
    public int countLatticePoints(int[][] circles) {
        int count=0,n=200,m=200,p=circles.length;
        for(int i = 0;i <= n;i++){
            for(int j = 0;j <= m;j++){
                for(int k = 0 ;k < p;k++){
                    int a=Math.abs(circles[k][0]-i),b=Math.abs(circles[k][1]-j),c=circles[k][2];
                    if(a * a + b * b <= c * c){
                        count++;
                        break;
                    }
                }
            }
        }
        return count;
    }
}