【差分数组】个人练习-Leetcode-2249. Count Lattice Points Inside a Circle
题目链接:https://leetcode.cn/problems/count-lattice-points-inside-a-circle/description/
题目大意:给出一系列圆的圆心坐标和半径,求在这些圆内部(边缘也算)的格点的数量。
思路:简单的思路就是暴力遍历。稍微优化一下,就是缩小一下范围,确定x, y坐标的上下限。通过是能通过,但复杂度还是 O ( N 3 ) O(N^3) O(N3)左右。
看题解学到了差分数组法:
对每一个纵坐标 y y y,画一条横线,对于一个圆如过经过内部点,必然从左到右穿过两个横坐标 x 1 , x 2 x_1, x_2 x1,x2(在圆上的情况就是 x 1 = x 2 x_1=x_2 x1=x2)。
那么就对这个 y y y坐标的差分数组,经过左端点时+1,经过右端点时-1。那么之后只需要遍历 x x x坐标,保留一个和cur,当cur > 0时就在圆内。我们可以让 x 2 x_2 x2都往右偏移一位,这样对于在圆上的情况也能保证计算在内。
完整代码
class Solution {
public:int countLatticePoints(vector<vector<int>>& circles) {int maxx = 0, maxy = 0;for (auto ck : circles) {maxx = max(maxx, ck[0] + ck[2]);maxy = max(maxy, ck[1] + ck[2]);}vector<vector<int>> d(maxy+1, vector<int>(maxx+2, 0));for (auto ck : circles) {int x = ck[0], y = ck[1], r = ck[2];for (int j = y+r, i1 = x, i2 = x; j >= y; j--) {while ((i1-x)*(i1-x) + (j-y)*(j-y) <= r*r)i1--;while ((i2-x)*(i2-x) + (j-y)*(j-y) <= r*r)i2++;i1++;d[j][i1]++;d[j][i2]--;}for (int j = y-r, i1 = x, i2 = x; j < y; j++) {while ((i1-x)*(i1-x) + (j-y)*(j-y) <= r*r)i1--;while ((i2-x)*(i2-x) + (j-y)*(j-y) <= r*r)i2++;i1++;d[j][i1]++;d[j][i2]--;}}int res = 0;for (int j = 0; j <= maxy; j++) {for (int i = 0, cur = 0; i <= maxx; i++){cur += d[j][i];if (cur > 0)res++;}}return res;}
};
相关文章:
【差分数组】个人练习-Leetcode-2249. Count Lattice Points Inside a Circle
题目链接:https://leetcode.cn/problems/count-lattice-points-inside-a-circle/description/ 题目大意:给出一系列圆的圆心坐标和半径,求在这些圆内部(边缘也算)的格点的数量。 思路:简单的思路就是暴力…...
【JavaEE】Cookie和Session详解
一.Cookie 首先我们知道HTTP协议本身是’‘无状态’‘的, 这里的’‘无状态’指的是:默认情况下HTTP协议的客户端和服务器之间的这次通信,和下次通信之间没有直接的联系. 但是在实际的开发过程之中, 我们很多时候是需要知道请求之间的关联关系的. 例如登陆网站成功后,第二次访…...
uniapp canvas vue3 ts实例
<template><view><canvas canvas-idcanvas-test class"canvas-test"></canvas></view> </template><script setup lang"ts">//封装的jsimport libs from /libs;//重点引入的import type { ComponentInternalIns…...
网络构建关键技术_3.SDN技术
SDN网络在控制平面和转发平面分别采用了不同技术,以满足SDN网络控件的全局性和灵活性,业务转发的高效性及高性价比要求。主要关键技术包括:控制平面技术、数据平面技术和转发规则一致性更新技术等。 1.控制平面技术 控制器是控制平面核心部件…...
【高性能服务器】单进程服务器
🔥博客主页: 我要成为C领域大神🎥系列专栏:【C核心编程】 【计算机网络】 【Linux编程】 【操作系统】 ❤️感谢大家点赞👍收藏⭐评论✍️ 本博客致力于知识分享,与更多的人进行学习交流 单进程服务器 …...
任意密码重置漏洞
文章目录 1. 任意密码重置漏洞原理2. 任意密码重置漏洞产生原因3. 任意密码重置漏洞场景3.1 验证码爆破3.2 验证凭证回传3.3 验证凭证未绑是用户3.4 跳过验证步骤3.5 凭证可预测3.6 同时向多个账户发送凭证 4. 任意密码重置经典案例4.1 中国人寿某重要系统任意账户密码重置4.2 …...
synchronized关键字和ReentrantLock在不同jdk版本中性能哪个高?该怎么选择呢?
synchronized关键字和ReentrantLock在不同JDK版本中的性能差异经历了显著的变化。早期,在JDK 1.5及以前的版本中,ReentrantLock通常提供了更好的性能,主要是因为synchronized关键字的实现较为简单,没有太多的优化,导致…...
【旭日x3派】部署官方yolov5全流程
地平线旭日x3派部署yolov5--全流程 前言一、深度学习环境安装二、安装docker三、部署3.1、安装工具链镜像3.2、配置天工开物OpenExplorer工具包3.3、创建深度学习虚拟空间,安装依赖:3.4、下载yolov5项目源码并运行3.5、pytorch的pt模型文件转onnx3.6、最…...
java LinkedList 怎么保证线程安全
在 Java 中,LinkedList 本身并不是线程安全的。如果需要在多线程环境中使用 LinkedList,可以采取以下几种方法来保证线程安全性: 1. 使用 Collections.synchronizedList Java 提供了一个实用的方法 Collections.synchronizedList 来包装 Li…...
uniapp+vue3开发微信小程序踩坑集
本文主要记录使用uniappvue3开发微信小程序遇见的各种常见问题及注意点。(持续更新) 问题: 自定义组件为什么有些样式加不上去 给自定义组件增加class的时候,有时候不生效有时候生效,一度让我怀疑自己记忆错乱。后来…...
办公软件WPS与Office的区别
临近计算机考试很多同学在纠结我是报wps好?还是ms office好?下面就来详细说说。 1、wps属于国内金山公司的办公软件,里面包含word、Excel和PPT。考试是2021年开始的! 2、MS(Microsoft 微软) office属于美…...
[数据集][目标检测]睡岗检测数据集VOC+YOLO格式3290张4类别
数据集格式:Pascal VOC格式YOLO格式(不包含分割路径的txt文件,仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数):3316 标注数量(xml文件个数):3316 标注数量(txt文件个数):3316 标注…...
使用Java编写网络爬虫
使用Java编写网络爬虫 大家好,我是免费搭建查券返利机器人省钱赚佣金就用微赚淘客系统3.0的小编,也是冬天不穿秋裤,天冷也要风度的程序猿! 网络爬虫是一种自动化程序,用于从互联网上获取信息并收集数据。在Java中编写…...
生鲜水果行业wordpress主题
水果蔬菜wordpress外贸自建站模板 水果、脐橙、牛油果、菠萝、凤梨、鲜枣、苹果、芒果、瓜果、百香果wordpress外贸独立站模板。 https://www.jianzhanpress.com/?p3932 生鲜wordpress外贸出口网站模板 水果、蔬菜、肉蛋奶、水产、干货等生鲜产品wordpress外贸出口公司网站…...
3.3V到5V的负电源产生电路(电荷泵电压反相器)SGM3204输出电流0.2A封装SOT23-6
前言 SGM3204 非稳压 200mA 电荷泵负电源产生电路,LCEDA原理图请访问资源 SGM3204电荷泵负电源产生电路 SGM3204电荷泵负电源产生电路 一般描述 SGM3204从 1.4V 至 5.5V 的输入电压范围产生非稳压负输出电压。 该器件通常由 5V 或 3.3V 的预稳压电源轨供电。由于…...
Excel 宏录制与VBA编程 —— 15、MsgBox参数详解
Msgbox参数具体如下 Msgbox参数使用1 Msgbox参数使用2(返回值示例) &ensp ;###### 关注 笔者 - jxd...
Kafka~消息发送过程与ISR机制了解
消息发送过程 使用Kafka发送消息时,一般有两种方式分别是: 同步发送异步发送 同步发送时,可以在发送消息后,通过get方法等待消息结果,这种情况能够准确的拿到消息最终的发送结果,要么是成功、要么是失败…...
multiprocessing.Queue 多个进程生产和多个进程消费怎么处理
在这个示例中,我们创建了一个队列 q,并通过 multiprocessing.Manager().Queue() 来确保队列可以在多个进程之间共享。我们定义了 consumer 和 producer 函数,分别用于从队列中获取数据和向队列中放入数据。 在主进程中,我们创建了…...
配置 Python 解释器及虚拟环境
配置 Python 解释器及虚拟环境 配置 Python 解释器: 1. 打开 PyCharm,进入“File”(文件)菜单,选择“Settings”(设置)。 2. 在弹出的设置窗口中,选择“Project: [项目名称]”下的…...
JeecgBoot中如何对敏感信息进行脱敏处理?
数据脱敏即将一些敏感信息通过加密、格式化等方式处理,展示给用户一个新的或是格式化后的信息,避免了敏感信息的暴露。 一、接口脱敏注解 针对接口数据实现脱敏加密,只加密,一般此方案用于数据加密展示。 1.1 注解介绍 注解作用域…...
java 实现excel文件转pdf | 无水印 | 无限制
文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...
CocosCreator 之 JavaScript/TypeScript和Java的相互交互
引擎版本: 3.8.1 语言: JavaScript/TypeScript、C、Java 环境:Window 参考:Java原生反射机制 您好,我是鹤九日! 回顾 在上篇文章中:CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...
【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验
系列回顾: 在上一篇中,我们成功地为应用集成了数据库,并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了!但是,如果你仔细审视那些 API,会发现它们还很“粗糙”:有…...
在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案
这个问题我看其他博主也写了,要么要会员、要么写的乱七八糟。这里我整理一下,把问题说清楚并且给出代码,拿去用就行,照着葫芦画瓢。 问题 在继承QWebEngineView后,重写mousePressEvent或event函数无法捕获鼠标按下事…...
mac 安装homebrew (nvm 及git)
mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用: 方法一:使用 Homebrew 安装 Git(推荐) 步骤如下:打开终端(Terminal.app) 1.安装 Homebrew…...
如何应对敏捷转型中的团队阻力
应对敏捷转型中的团队阻力需要明确沟通敏捷转型目的、提升团队参与感、提供充分的培训与支持、逐步推进敏捷实践、建立清晰的奖励和反馈机制。其中,明确沟通敏捷转型目的尤为关键,团队成员只有清晰理解转型背后的原因和利益,才能降低对变化的…...
破解路内监管盲区:免布线低位视频桩重塑停车管理新标准
城市路内停车管理常因行道树遮挡、高位设备盲区等问题,导致车牌识别率低、逃费率高,传统模式在复杂路段束手无策。免布线低位视频桩凭借超低视角部署与智能算法,正成为破局关键。该设备安装于车位侧方0.5-0.7米高度,直接规避树枝遮…...
抽象类和接口(全)
一、抽象类 1.概念:如果⼀个类中没有包含⾜够的信息来描绘⼀个具体的对象,这样的类就是抽象类。 像是没有实际⼯作的⽅法,我们可以把它设计成⼀个抽象⽅法,包含抽象⽅法的类我们称为抽象类。 2.语法 在Java中,⼀个类如果被 abs…...
五子棋测试用例
一.项目背景 1.1 项目简介 传统棋类文化的推广 五子棋是一种古老的棋类游戏,有着深厚的文化底蕴。通过将五子棋制作成网页游戏,可以让更多的人了解和接触到这一传统棋类文化。无论是国内还是国外的玩家,都可以通过网页五子棋感受到东方棋类…...
sshd代码修改banner
sshd服务连接之后会收到字符串: SSH-2.0-OpenSSH_9.5 容易被hacker识别此服务为sshd服务。 是否可以通过修改此banner达到让人无法识别此服务的目的呢? 不能。因为这是写的SSH的协议中的。 也就是协议规定了banner必须这么写。 SSH- 开头,…...
