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

【康复学习--LeetCode每日一题】3111. 覆盖所有点的最少矩形数目

题目:

给你一个二维整数数组 point ,其中 points[i] = [xi, yi] 表示二维平面内的一个点。同时给你一个整数 w 。你需要用矩形 覆盖所有 点。

每个矩形的左下角在某个点 (x1, 0) 处,且右上角在某个点 (x2, y2) 处,其中 x1 <= x2 且 y2 >= 0 ,同时对于每个矩形都 必须 满足 x2 - x1 <= w 。

如果一个点在矩形内或者在边上,我们说这个点被矩形覆盖了。

请你在确保每个点都 至少 被一个矩形覆盖的前提下,最少 需要多少个矩形。

注意:一个点可以被多个矩形覆盖。

示例 1:
在这里插入图片描述
输入:points = [[2,1],[1,0],[1,4],[1,8],[3,5],[4,6]], w = 1
输出:2
解释:
上图展示了一种可行的矩形放置方案:
一个矩形的左下角在 (1, 0) ,右上角在 (2, 8) 。
一个矩形的左下角在 (3, 0) ,右上角在 (4, 8) 。

示例 2:
在这里插入图片描述
输入:points = [[0,0],[1,1],[2,2],[3,3],[4,4],[5,5],[6,6]], w = 2
输出:3
解释:
上图展示了一种可行的矩形放置方案:
一个矩形的左下角在 (0, 0) ,右上角在 (2, 2) 。
一个矩形的左下角在 (3, 0) ,右上角在 (5, 5) 。
一个矩形的左下角在 (6, 0) ,右上角在 (6, 6) 。

示例 3:
在这里插入图片描述
输入:points = [[2,3],[1,2]], w = 0
输出:2
解释:
上图展示了一种可行的矩形放置方案:
一个矩形的左下角在 (1, 0) ,右上角在 (1, 2) 。
一个矩形的左下角在 (2, 0) ,右上角在 (2, 3) 。

提示:
1 <= points.length <= 105
points[i].length==2
0 <= xi ==points[i][0] <= 109
0 <= yi == points[i][1] <= 109
0 <= w <= 109
所有点坐标 (xi, yi) 互不相同。

思路:

贪心,按横坐标从小打到排序,查看需要多少次能将横坐标全部覆盖,每次和x+w进行比较,x+w内代表都可覆盖,超过此范围的则代表需要一个新矩形。

代码:

class Solution {//贪心 横坐标需要几个矩形可以覆盖public int minRectanglesToCoverPoints(int[][] points, int w) {// 按横坐标从小到大排序Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));int ans = 0;// 每次用x+w来更新边界值int bound = -1;for (int[] p : points) {if (p[0] > bound) {bound = p[0] + w;ans++;}}return ans;}
}

相关文章:

【康复学习--LeetCode每日一题】3111. 覆盖所有点的最少矩形数目

题目&#xff1a; 给你一个二维整数数组 point &#xff0c;其中 points[i] [xi, yi] 表示二维平面内的一个点。同时给你一个整数 w 。你需要用矩形 覆盖所有 点。 每个矩形的左下角在某个点 (x1, 0) 处&#xff0c;且右上角在某个点 (x2, y2) 处&#xff0c;其中 x1 < x…...

Django实战:开启数字化任务管理的新纪元

&#x1f680; Django实战&#xff1a;开启数字化任务管理的新纪元 &#x1f310; &#x1f4d6; 引言 在数字化转型的浪潮中&#xff0c;任务管理的智能化成为提升组织效能的关键。今天&#xff0c;我将带领大家深入了解我们最新开发的OFTS系统——一款创新的组织任务管理软…...

史上最全网络安全面试题+答案

1、什么是SQL注入攻击 前端代码未被解析被代入到数据库导致数据库报错 2、什么是XSS攻击 跨站脚本攻击 在网页中嵌入客户端恶意脚本&#xff0c;常用s语言&#xff0c;也会用其他脚本语言 属于客户端攻击&#xff0c;受害者是用户&#xff0c;网站管理员也属于用户&#xf…...

Python 爬虫入门(五):使用 lxml 解析网页

Python 爬虫入门&#xff08;五&#xff09;&#xff1a;使用 lxml 解析网页 前言1. lxml 简介1.1 什么是 lxml&#xff1f;1.2 为什么选择 lxml&#xff1f;1.3 安装 lxml 2. lxml 基础2.1 解析 HTML/XML2.2 XPath 表达式2.3 使用 XPath 提取数据 3. 深入解析3.1 处理命名空间…...

阿里云RDS到亚马逊云RDS的实时数据同步方案详解

1. 需求背景 在当今的多云环境中,企业经常需要在不同云平台之间同步数据。本文将详细介绍如何实现从阿里云RDS MySQL数据库到亚马逊云RDS MySQL数据库的实时数据同步。这种同步对于数据备份、跨区域数据访问、数据分析等场景都非常有用。 2. 方案概述 我们将使用AWS Kinesis…...

《LeetCode热题100》---<滑动窗口篇两道>

本篇博客讲解LeetCode热题100道滑动窗口篇中的两道题 第一道&#xff1a;无重复字符的最长子串 第二道&#xff1a;找到字符当中的所有字母异位词 第一道&#xff1a;无重复字符的最长子串 哈希滑动窗口 class Solution {public int lengthOfLongestSubstring(String s0) {int…...

Python学习计划——9.1多线程编程

并发编程是一种在同一时间段内运行多个任务的方法&#xff0c;可以提高程序的效率和性能。Python中的多线程编程可以使用threading模块实现。以下是多线程编程的详细讲解和可运行的Python案例。 1. 什么是多线程 多线程是一种并发编程的方式&#xff0c;它允许在同一个进程中…...

借助 NGINX 对本地的 Kubernetes 服务进行自动化的 TCP 负载均衡

原文作者&#xff1a;Chris Akker - F5 技术解决方案架构师&#xff0c;Steve Wagner - F5 NGINX 解决方案架构师 原文链接&#xff1a;借助 NGINX 对本地的 Kubernetes 服务进行自动化的 TCP 负载均衡 转载来源&#xff1a;NGINX 中文官网 NGINX 唯一中文官方社区 &#xff0c…...

基于python的大学学生影响力分析系统设计与实现

博主介绍&#xff1a; 大家好&#xff0c;本人精通Java、Python、C#、C、C编程语言&#xff0c;同时也熟练掌握微信小程序、Php和Android等技术&#xff0c;能够为大家提供全方位的技术支持和交流。 我有丰富的成品Java、Python、C#毕设项目经验&#xff0c;能够为学生提供各类…...

upload-labs靶场(1-19关)

upload-labs靶场 简介 upload-labs是一个使用php语言编写的&#xff0c;专门收集渗透测试过程中遇到的各种上传漏洞的靶场。旨在帮助大家对上传漏洞有一个全面的了解。目前一共19关&#xff0c;每一关都包含着不同上传方式。 注意&#xff1a;能运行<?php phpinfo();?&…...

Python面向对象浅析

目录 面向对象基本概念 一、类和对象 类和对象是面向对象骗程的两个核心概念。 在程序开发中&#xff0c;要设计一个类&#xff0c;通常需要满足一下三个要素: self详解&#xff1a; 对象&#xff08;Object&#xff09; 魔法方法&#xff1a; 类里的一些特殊方法 __in…...

JS基本语法

JS代码写在body结束标签的上面 如点击按钮调用方法&#xff1a; 在浏览器的控制台打印测试数据 console.log() <body><button type"button" onclick"easymethod()">点击我</button><script>//JS代码&#xff0c;写在body标签的…...

LSTM详解总结

LSTM&#xff08;Long Short-Term Memory&#xff09;是一种用于处理和预测时间序列数据的递归神经网络&#xff08;RNN&#xff09;的改进版本。其设计初衷是为了解决普通RNN在长序列训练中出现的梯度消失和梯度爆炸问题。以下是对LSTM的详细解释&#xff0c;包括原理、公式、…...

制品库nexus

详见&#xff1a;Sonatype Nexus Repository搭建与使用&#xff08;详细教程3.70.1&#xff09;-CSDN博客 注意事项&#xff1a; 1.java8环境使用nexus-3.69.0-02-java8-unix.tar.gz包 2.java11环境使用nexus-3.70.1-02-java11-unix.tar.gz包 3.注意使用制品库/etc/yum.repos.…...

2022.11.17 阿里钉钉数据开发岗位一面

今天晚上和阿里钉钉面试官聊了一面&#xff0c;整个过程持续45分钟&#xff0c;还是相当持久的。前面先让我自我介绍&#xff0c;包括自身背景、工作经历和项目经验&#xff0c;在介绍的时候面试官几次打断&#xff0c;让我停下来&#xff0c;然后他提问&#xff0c;我很纳闷还…...

【无标题】Git(仓库,分支,分支冲突)

Git 一种分布式版本控制系统&#xff0c;用于跟踪和管理代码的变更 一&#xff0e;Git的主要功能&#xff1a; 二&#xff0e;准备git机器 修改静态ip&#xff0c;主机名 三&#xff0e;git仓库的建立&#xff1a; 1.安装git [rootgit ~]# yum -y install git 2.创建一个…...

访问控制列表(ACL)

文章目录 ACL原理与基本配置ACL分类ACL组成ACL规则的匹配与应用 ACL原理与基本配置 ACL(Access Control List&#xff0c;访问控制列表) 读取二层、三层、四层报文信息根据预先定义好的规则对报文进行过滤和分类实现网络访问控制、防止网络攻击和提高网络带宽利用率等目的提高…...

自用git命令(待完善)

----------------------------------------------------------------------------------------- ###基础 git config --global user.name "xxxxx" #设置提交人 name git config --global user.email "xxxxxx163.com" #设置提交人 email git …...

突破•指针四

听说这是目录哦 函数指针数组&#x1fae7;用途&#xff1a;转移表 回调函数&#x1fae7;能量站&#x1f61a; 函数指针数组&#x1fae7; 函数指针数组是存放函数地址的数组&#xff0c;例如int (*parr[5])()中parr先和[]结合&#xff0c;说明parr是可以存放5个函数地址【元…...

深入解析Python `requests`库源码,揭开HTTP请求的神秘面纱!

&#x1f538; 第一部分&#xff1a;requests库的入口 我们从requests库的入口开始&#xff0c;通常我们会使用 requests.get() 或 requests.post() 等方法发送HTTP请求。那么&#xff0c;这些方法背后究竟做了些什么呢&#xff1f;我们从requests.get()方法开始看起&#xff…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

UE5 学习系列(三)创建和移动物体

这篇博客是该系列的第三篇&#xff0c;是在之前两篇博客的基础上展开&#xff0c;主要介绍如何在操作界面中创建和拖动物体&#xff0c;这篇博客跟随的视频链接如下&#xff1a; B 站视频&#xff1a;s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...

Robots.txt 文件

什么是robots.txt&#xff1f; robots.txt 是一个位于网站根目录下的文本文件&#xff08;如&#xff1a;https://example.com/robots.txt&#xff09;&#xff0c;它用于指导网络爬虫&#xff08;如搜索引擎的蜘蛛程序&#xff09;如何抓取该网站的内容。这个文件遵循 Robots…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)

🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包

文章目录 现象&#xff1a;mysql已经安装&#xff0c;但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时&#xff0c;可能是因为以下几个原因&#xff1a;1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...

图表类系列各种样式PPT模版分享

图标图表系列PPT模版&#xff0c;柱状图PPT模版&#xff0c;线状图PPT模版&#xff0c;折线图PPT模版&#xff0c;饼状图PPT模版&#xff0c;雷达图PPT模版&#xff0c;树状图PPT模版 图表类系列各种样式PPT模版分享&#xff1a;图表系列PPT模板https://pan.quark.cn/s/20d40aa…...

#Uniapp篇:chrome调试unapp适配

chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器&#xff1a;Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...

代码随想录刷题day30

1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币&#xff0c;另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额&#xff0c;返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...