当前位置: 首页 > news >正文

算法刷题打卡第91天:统计一个圆中点的数目

统计一个圆中点的数目

难度:中等

给你一个数组 points ,其中 points[i] = [xi, yi] ,表示第 i 个点在二维平面上的坐标。多个点可能会有 相同 的坐标。

同时给你一个数组 queries ,其中 queries[j] = [xj, yj, rj] ,表示一个圆心在 (xj, yj) 且半径为 rj 的圆。

对于每一个查询 queries[j] ,计算在第 j 个圆 点的数目。如果一个点在圆的 边界上 ,我们同样认为它在圆

请你返回一个数组 answer ,其中 answer[j] 是第 j 个查询的答案。

示例 1:

请添加图片描述

输入:points = [[1,3],[3,3],[5,3],[2,2]], queries = [[2,3,1],[4,3,1],[1,1,2]]
输出:[3,2,2]
解释:所有的点和圆如上图所示。
queries[0] 是绿色的圆,queries[1] 是红色的圆,queries[2] 是蓝色的圆。

示例 2:

请添加图片描述

输入:points = [[1,1],[2,2],[3,3],[4,4],[5,5]], queries = [[1,2,2],[2,2,2],[4,3,2],[4,3,3]]
输出:[2,3,2,4]
解释:所有的点和圆如上图所示。
queries[0] 是绿色的圆,queries[1] 是红色的圆,queries[2] 是蓝色的圆,queries[3] 是紫色的圆。

枚举每个点是否在每个圆中

思路:

我们可以使用二重循环,对于每一个查询,枚举所有的点,依次判断它们是否在查询的圆中即可。

如果查询圆的圆心为 (cx,cy)(c_x, c_y)(cx,cy),半径为 crc_rcr,枚举的点坐标为 (px,py)(p_x, p_y)(px,py),那么点在圆中(包括在圆上的情况)当且仅当点到圆心的距离小于等于半径。我们可以用以下方法进行判断:

(cx−px)2+(cy−py)2≤cr2(c_x-p_x)^2 + (c_y-p_y)^2 \leq c_r^2(cxpx)2+(cypy)2cr2

注意这里两侧的距离都进行了平方操作,这样可以避免引入浮点数,产生不必要的误差。

复杂度分析:

  • 时间复杂度: O(mn)O(mn)O(mn),其中 mmmnnn 分别是数组 points\textit{points}pointsqueries\textit{queries}queries 的长度。
  • 空间复杂度: O(1)O(1)O(1)
class Solution:def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:res = []for i in queries:count = 0for j in points:if pow((i[0] - j[0]) ** 2 + (i[1] - j[1]) ** 2, 1/2) <= i[2]:count += 1res.append(count)return res

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/queries-on-number-of-points-inside-a-circle

相关文章:

算法刷题打卡第91天:统计一个圆中点的数目

统计一个圆中点的数目 难度&#xff1a;中等 给你一个数组 points &#xff0c;其中 points[i] [xi, yi] &#xff0c;表示第 i 个点在二维平面上的坐标。多个点可能会有 相同 的坐标。 同时给你一个数组 queries &#xff0c;其中 queries[j] [xj, yj, rj] &#xff0c;表…...

sentinel持久化方案

一.sentinel规则推送原理 1.原有内存规则存储原理 (1)dashborad中请求到服务器后&#xff0c;在controller中通过http把规则直接推送给client&#xff0c;client接收后把规则放入内存&#xff1b; 2.持久化推送规则原理 ![在这里插入代码片](https://img-blog.csdnimg.cn/1…...

软件项目进度安排与跟踪:关键路径的计算

在一个软件项目中&#xff0c;管理人员需要按时了解项目进度&#xff0c;制定项目计划&#xff0c;同时需要及时发现所遇到的问题&#xff0c;然后和团队成员制定解决方案&#xff0c;确保整个计划可以顺利的进行&#xff0c;因此项目进度安排与跟踪是项目管理中的一个重要环节…...

mac m2 处理器 iterm2 sz rz 出错/无限重试

mac m2 处理器 iterm2 sz rz 出错/无限重试 1、背景 apple m 系列处理器安装的 homebrew 跟 intel 处理器略有不同&#xff0c;其中安装目录的区别&#xff1a; m 系列处理器安装目录为 /usr/local/bin/homebrewintel 处理器安装目录为 /opt/homebrew 其中 m 系列处理器安装…...

Mysql 与 磁盘交互的过程

从之前的Mysql架构可以了解到&#xff0c;Mysql 客户端不是直接和磁盘打交道&#xff0c;我们在客户端输入的sql语句会被发送给服务端&#xff0c;服务端对sql语句进行解析、缓存等操作&#xff0c;然后再交由存储引擎去读写磁盘。这其实是从 C/S 的角度去了解Mysql。 站在OS的…...

Spring Cloud Gateway集成Nacos实现负载均衡

&#x1f4a1;Nacas可以用于实现Spring Cloud Gateway中网关动态路由功能&#xff0c;也可以基于Nacos来实现对后端服务的负载均衡&#xff0c;前者利用Nacos配置中心功能&#xff0c;后者利用Nacos服务注册功能。接下来我们来看下Gateway集成Nacos实现负载均衡的架构图一. 环境…...

Excel图表教程_编程入门自学教程_菜鸟教程-免费教程分享

教程简介 Excel图表初学者教程 - 从简单和简单的步骤学习Excel图表从基本概念到高级概念&#xff0c;包括简介&#xff0c;创建图表&#xff0c;类型&#xff0c;柱形图&#xff0c;折线图&#xff0c;饼图&#xff0c;圆环图&#xff0c;条形图&#xff0c;面积图&#xff0c…...

2023最新的接口自动化测试面试题

1、请结合你熟悉的项目&#xff0c;介绍一下你是怎么做测试的&#xff1f; -首先要自己熟悉项目&#xff0c;熟悉项目的需求、项目组织架构、项目研发接口等 -功能 接口 自动化 性能 是怎么处理的&#xff1f; -第一步&#xff1a; 进行需求分析&#xff0c;需求评审&#…...

AcWing语法基础课笔记 第一章 C++入门及简单的顺序结构

第一章 C入门及简单的顺序结构 编程是一种控制计算机的方式&#xff0c;和我们平时双击打开文件、关机、重启没有任何区别。 ———闫学灿 C中常用的变量类型 和所占字节大小 输出变量地址符&#xff1a; 软件环境 作业的评测与提交 在线练习地址&#xff1a;www.acwing.com …...

【并发编程】【2】进程与线程

并发编程 2.进程与线程 2.1 进程与线程 进程 程序由指令和数据组成&#xff0c;但这些指令要运行&#xff0c;数据要读写&#xff0c;就必须将指令加载至 CPU&#xff0c;数据加载至内存。在 指令运行过程中还需要用到磁盘、网络等设备。进程就是用来加载指令、管理内存、管…...

MySQL获取当前时间的各种方式

1 获取当前完整时间1.1 now()函数select now();输出:2023-02-15 10:46:171.2 sysdate()函数select sysdate();输出:2023-02-15 10:47:131.3 current_timestamp或current_timestamp()current_timestamp和current_timestamp()函数的效果是一样的&#xff0c;只不过一个是关键字&a…...

redis持久化之AOF(Append Only File)及其总结

1.是什么&#xff1f; 以日志的形式来记录每个写操作&#xff0c;将redis执行过的所有写指令记录下来(读操作不记录)&#xff0c;只许追加文件但不可以改写文件&#xff0c;redis启动之初会读取该文件重新构建数据&#xff0c;换言之&#xff0c;redis重启的话就根据日志文件的…...

LeetCode 刷题之队列

5. 队列 队列&#xff08;queue&#xff09;是只允许在一端进行插入操作&#xff0c;而在另一端进行删除操作的线性表。 队列是一种先进先出的&#xff08;First In First Out&#xff09;的线性表&#xff0c;简称 FIFO。允许插入的一端为队尾&#xff0c;允许删除的一端为队…...

互联网摸鱼日报(2023-02-15)

互联网摸鱼日报&#xff08;2023-02-15&#xff09; InfoQ 热门话题 ChatGPT火爆全球后&#xff0c;OpenAI CEO称“它很酷&#xff0c;但却是个糟糕的产品” 微软发言人证实旗下LinkedIn平台开始裁员 Akamai 推出 Akamai Connected Cloud 和全新云计算服务 AI赋能元宇宙游戏…...

聊聊外包和远程项目的敏捷管理(合辑共7篇)

这是鼎叔的第五十一篇原创文章。行业大牛和刚毕业的小白&#xff0c;都可以进来聊聊。欢迎关注本专栏和微信公众号《敏捷测试转型》&#xff0c;大量原创思考文章陆续推出。第四个合辑完工了&#xff0c;咱们介绍了外包管理或远程项目如何敏捷交付&#xff0c;满足管理层预期。…...

2023-2-15 刷题情况

检查「好数组」 题目描述 给你一个正整数数组 nums&#xff0c;你需要从中任选一些子集&#xff0c;然后将子集中每一个数乘以一个 任意整数&#xff0c;并求出他们的和。 假如该和结果为 1&#xff0c;那么原数组就是一个「好数组」&#xff0c;则返回 True&#xff1b;否则…...

汉诺塔递归算法精讲

文章目录前言一、汉诺塔是个啥&#xff1f;二、手动解法三、解法抽象四、递归解法五、总结前言 递归算法是计算机算法中的基础算法&#xff0c;也是非常重要的算法&#xff0c;从某种程度上讲&#xff0c;它有一点儿AI的影子。人脑是可以完成递归思路的&#xff0c;但是对不起…...

vue的$nextTick的原理

参考&#xff1a;https://cloud.tencent.com/developer/article/1633546 总结一下&#xff1a;就是$nextTick将回调函数放到微任务或者宏任务当中以延迟它地执行顺序&#xff1b;&#xff08;总结的也比较懒&#x1f476;&#xff09; 重要的是理解源码中它的三个参数的意思&a…...

前端学习第一阶段——第五章CSS(下)

5-9 浮动 08-浮动导读 09-传统网页布局三种方式 10-为什么需要浮动 11-什么是浮动 12-浮动特性-脱标 13-浮动特性-浮动元素一行显示 14-浮动特性-浮动元素具有行内块特性 15-浮动元素经常搭配标准流的父元素 16-浮动布局练习1 <!DOCTYPE html> <html lang"en&quo…...

基于django搭建简单的个人博客

文章目录第一步、在Ubuntu中安装虚拟环境并进入第二步、安装blog所需要的包&#xff0c;在requirements.txt中安装mysqlclient可能会报错&#xff0c;输入下列命令后在安装即可成功第三步、创建好数据库&#xff0c;把测试数据导入第四步、修改DjangoBlog包中 settings中数据库…...

超短脉冲激光自聚焦效应

前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应&#xff0c;这是一种非线性光学现象&#xff0c;主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场&#xff0c;对材料产生非线性响应&#xff0c;可能…...

【kafka】Golang实现分布式Masscan任务调度系统

要求&#xff1a; 输出两个程序&#xff0c;一个命令行程序&#xff08;命令行参数用flag&#xff09;和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽&#xff0c;然后将消息推送到kafka里面。 服务端程序&#xff1a; 从kafka消费者接收…...

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战

在现代战争中&#xff0c;电磁频谱已成为继陆、海、空、天之后的 “第五维战场”&#xff0c;雷达作为电磁频谱领域的关键装备&#xff0c;其干扰与抗干扰能力的较量&#xff0c;直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器&#xff0c;凭借数字射…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...

精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南

精益数据分析&#xff08;97/126&#xff09;&#xff1a;邮件营销与用户参与度的关键指标优化指南 在数字化营销时代&#xff0c;邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天&#xff0c;我们将深入解析邮件打开率、网站可用性、页面参与时…...

Java线上CPU飙高问题排查全指南

一、引言 在Java应用的线上运行环境中&#xff0c;CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时&#xff0c;通常会导致应用响应缓慢&#xff0c;甚至服务不可用&#xff0c;严重影响用户体验和业务运行。因此&#xff0c;掌握一套科学有效的CPU飙高问题排查方法&…...

蓝桥杯 冶炼金属

原题目链接 &#x1f527; 冶炼金属转换率推测题解 &#x1f4dc; 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V&#xff0c;是一个正整数&#xff0c;表示每 V V V 个普通金属 O O O 可以冶炼出 …...

C++.OpenGL (20/64)混合(Blending)

混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...

uniapp手机号一键登录保姆级教程(包含前端和后端)

目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号&#xff08;第三种&#xff09;后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...