【康复学习--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. 覆盖所有点的最少矩形数目
题目: 给你一个二维整数数组 point ,其中 points[i] [xi, yi] 表示二维平面内的一个点。同时给你一个整数 w 。你需要用矩形 覆盖所有 点。 每个矩形的左下角在某个点 (x1, 0) 处,且右上角在某个点 (x2, y2) 处,其中 x1 < x…...
Django实战:开启数字化任务管理的新纪元
🚀 Django实战:开启数字化任务管理的新纪元 🌐 📖 引言 在数字化转型的浪潮中,任务管理的智能化成为提升组织效能的关键。今天,我将带领大家深入了解我们最新开发的OFTS系统——一款创新的组织任务管理软…...
史上最全网络安全面试题+答案
1、什么是SQL注入攻击 前端代码未被解析被代入到数据库导致数据库报错 2、什么是XSS攻击 跨站脚本攻击 在网页中嵌入客户端恶意脚本,常用s语言,也会用其他脚本语言 属于客户端攻击,受害者是用户,网站管理员也属于用户…...
Python 爬虫入门(五):使用 lxml 解析网页
Python 爬虫入门(五):使用 lxml 解析网页 前言1. lxml 简介1.1 什么是 lxml?1.2 为什么选择 lxml?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道滑动窗口篇中的两道题 第一道:无重复字符的最长子串 第二道:找到字符当中的所有字母异位词 第一道:无重复字符的最长子串 哈希滑动窗口 class Solution {public int lengthOfLongestSubstring(String s0) {int…...
Python学习计划——9.1多线程编程
并发编程是一种在同一时间段内运行多个任务的方法,可以提高程序的效率和性能。Python中的多线程编程可以使用threading模块实现。以下是多线程编程的详细讲解和可运行的Python案例。 1. 什么是多线程 多线程是一种并发编程的方式,它允许在同一个进程中…...
借助 NGINX 对本地的 Kubernetes 服务进行自动化的 TCP 负载均衡
原文作者:Chris Akker - F5 技术解决方案架构师,Steve Wagner - F5 NGINX 解决方案架构师 原文链接:借助 NGINX 对本地的 Kubernetes 服务进行自动化的 TCP 负载均衡 转载来源:NGINX 中文官网 NGINX 唯一中文官方社区 ,…...
基于python的大学学生影响力分析系统设计与实现
博主介绍: 大家好,本人精通Java、Python、C#、C、C编程语言,同时也熟练掌握微信小程序、Php和Android等技术,能够为大家提供全方位的技术支持和交流。 我有丰富的成品Java、Python、C#毕设项目经验,能够为学生提供各类…...
upload-labs靶场(1-19关)
upload-labs靶场 简介 upload-labs是一个使用php语言编写的,专门收集渗透测试过程中遇到的各种上传漏洞的靶场。旨在帮助大家对上传漏洞有一个全面的了解。目前一共19关,每一关都包含着不同上传方式。 注意:能运行<?php phpinfo();?&…...
Python面向对象浅析
目录 面向对象基本概念 一、类和对象 类和对象是面向对象骗程的两个核心概念。 在程序开发中,要设计一个类,通常需要满足一下三个要素: self详解: 对象(Object) 魔法方法: 类里的一些特殊方法 __in…...
JS基本语法
JS代码写在body结束标签的上面 如点击按钮调用方法: 在浏览器的控制台打印测试数据 console.log() <body><button type"button" onclick"easymethod()">点击我</button><script>//JS代码,写在body标签的…...
LSTM详解总结
LSTM(Long Short-Term Memory)是一种用于处理和预测时间序列数据的递归神经网络(RNN)的改进版本。其设计初衷是为了解决普通RNN在长序列训练中出现的梯度消失和梯度爆炸问题。以下是对LSTM的详细解释,包括原理、公式、…...
制品库nexus
详见:Sonatype Nexus Repository搭建与使用(详细教程3.70.1)-CSDN博客 注意事项: 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 阿里钉钉数据开发岗位一面
今天晚上和阿里钉钉面试官聊了一面,整个过程持续45分钟,还是相当持久的。前面先让我自我介绍,包括自身背景、工作经历和项目经验,在介绍的时候面试官几次打断,让我停下来,然后他提问,我很纳闷还…...
【无标题】Git(仓库,分支,分支冲突)
Git 一种分布式版本控制系统,用于跟踪和管理代码的变更 一.Git的主要功能: 二.准备git机器 修改静态ip,主机名 三.git仓库的建立: 1.安装git [rootgit ~]# yum -y install git 2.创建一个…...
访问控制列表(ACL)
文章目录 ACL原理与基本配置ACL分类ACL组成ACL规则的匹配与应用 ACL原理与基本配置 ACL(Access Control List,访问控制列表) 读取二层、三层、四层报文信息根据预先定义好的规则对报文进行过滤和分类实现网络访问控制、防止网络攻击和提高网络带宽利用率等目的提高…...
自用git命令(待完善)
----------------------------------------------------------------------------------------- ###基础 git config --global user.name "xxxxx" #设置提交人 name git config --global user.email "xxxxxx163.com" #设置提交人 email git …...
突破•指针四
听说这是目录哦 函数指针数组🫧用途:转移表 回调函数🫧能量站😚 函数指针数组🫧 函数指针数组是存放函数地址的数组,例如int (*parr[5])()中parr先和[]结合,说明parr是可以存放5个函数地址【元…...
深入解析Python `requests`库源码,揭开HTTP请求的神秘面纱!
🔸 第一部分:requests库的入口 我们从requests库的入口开始,通常我们会使用 requests.get() 或 requests.post() 等方法发送HTTP请求。那么,这些方法背后究竟做了些什么呢?我们从requests.get()方法开始看起ÿ…...
设计模式和设计原则回顾
设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...
2025年能源电力系统与流体力学国际会议 (EPSFD 2025)
2025年能源电力系统与流体力学国际会议(EPSFD 2025)将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会,EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...
在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:
在 HarmonyOS 应用开发中,手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力,既支持点击、长按、拖拽等基础单一手势的精细控制,也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档,…...
Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件
今天呢,博主的学习进度也是步入了Java Mybatis 框架,目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学,希望能对大家有所帮助,也特别欢迎大家指点不足之处,小生很乐意接受正确的建议&…...
聊聊 Pulsar:Producer 源码解析
一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台,以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中,Producer(生产者) 是连接客户端应用与消息队列的第一步。生产者…...
2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面
代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口(适配服务端返回 Token) export const login async (code, avatar) > {const res await http…...
C# SqlSugar:依赖注入与仓储模式实践
C# SqlSugar:依赖注入与仓储模式实践 在 C# 的应用开发中,数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护,许多开发者会选择成熟的 ORM(对象关系映射)框架,SqlSugar 就是其中备受…...
CMake 从 GitHub 下载第三方库并使用
有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...
【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)
骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术,它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton):由层级结构的骨头组成,类似于人体骨骼蒙皮 (Mesh Skinning):将模型网格顶点绑定到骨骼上,使骨骼移动…...
Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?
Redis 的发布订阅(Pub/Sub)模式与专业的 MQ(Message Queue)如 Kafka、RabbitMQ 进行比较,核心的权衡点在于:简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...
