首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >LeetCode 2249. 统计圆内格点数目

LeetCode 2249. 统计圆内格点数目

作者头像
Michael阿明
发布于 2022-07-17 02:12:21
发布于 2022-07-17 02:12:21
25400
代码可运行
举报
运行总次数:0
代码可运行

文章目录

1. 题目

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

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

示例 1:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
输入:circles = [[2,2,1]]
输出:5
解释:
给定的圆如上图所示。
出现在圆内的格点为 (1, 2)(2, 1)(2, 2)(2, 3)  (3, 2),在图中用绿色标识。
 (1, 1)  (1, 3) 这样用红色标识的点,并未出现在圆内。
因此,出现在至少一个圆内的格点数目是 5

示例 2:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
输入: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/problems/count-lattice-points-inside-a-circle 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution:
    def countLatticePoints(self, circles: List[List[int]]) -> int:
        X = max(x+r for x,y,r in circles) # 最大的边界
        Y = max(y+r for x,y,r in circles) # 最大的边界
        ans = 0
        circles.sort(key=lambda x: x[-1], reverse=True) # 半径大的先找
        for x in range(X+1):
            for y in range(Y+1):
                for x0, y0, r in circles:
                    if (x-x0)*(x-x0) + (y-y0)*(y-y0) <= r*r:
                        ans += 1
                        break
        return ans

872 ms 14.9 MB Python3

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2022-07-16,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 文章目录
  • 1. 题目
  • 2. 解题
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档