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

LeetCode每日一题——2132.用邮票贴满网格图

参考资料:

  • 2132. 用邮票贴满网格图 - 力扣(LeetCode)

题目描述

给你一个 m x n 的二进制矩阵 grid ,每个格子要么为 0 (空)要么为 1 (被占据)。

给你邮票的尺寸为 stampHeight x stampWidth 。我们想将邮票贴进二进制矩阵中,且满足以下 限制要求

  1. 覆盖所有 格子。
  2. 不覆盖任何 被占据 的格子。
  3. 我们可以放入任意数目的邮票。
  4. 邮票可以相互有 重叠 部分。
  5. 邮票不允许 旋转
  6. 邮票必须完全在矩阵

如果在满足上述要求的前提下,可以放入邮票,请返回 true ,否则返回 false

样例

image-20231214141658463

思路

主要思想:二维前缀和 + 二维差分

由于题目没有限制放入邮票的数量,也允许邮票相互重叠,所以我们应该尽可能地多贴邮票

假设我们以邮票的左上角 (i,j)为基准粘贴邮票,则该邮票的覆盖范围是 (i.j) ~ (x,y) ,其中 x = i+stampHeight-1, y = j+stampHeight-1。为了铺满整张网格图,我们遍历每个格子,判断能否以当前格子为左上角粘贴邮票,最后,我们检查是否每个空格子都被邮票覆盖即可。关键问题在于:

  1. 如果快速判断一个矩形范围 (i.j) ~ (x,y) 内是否存在被占据的格子。
  2. 在贴上邮票后如何更新矩阵的状态,并在最后快速判断每个空格子是否被覆盖。

对于第一个问题,我们可以使用二维前缀和解决。定义 sum[i][j] 表示范围 (0,0) ~ (i,j) 内被占据格子的数量,那么对与我们要粘贴邮票的范围 (i.j) ~ (x,y) ,只需判断 sum[x][y]-sum[i-1][y]-sum[x][j-1]+sum[i-1][j-1] 是否为 0 即可。

对于第二个问题,我们可以使用二维差分解决。由于本人之前对于差分的理解不是很到位,所以这里展开说一下。差分可以看作前缀和的逆运算,我们对差分数组求前缀和即可得到原数组,对原数组求前缀和即可得到前缀和数组。假设这里的原数组 arr[i][j] 表示当前格子上的邮票数量,那差分数组 diff 就应该按照下图方式修改:

image-20231214145035029

代码

不得不承认,我求二维前缀和、二维差分的代码极其丑陋。。。

class Solution {
public:bool possibleToStamp(vector<vector<int>>& grid, int stampHeight, int stampWidth) {int m = grid.size(), n = grid[0].size();vector<vector<int>> sum(grid.begin(), grid.end());vector<vector<int>> diff(m, vector<int>(n, 0));for(int i=0;i<m;++i){for(int j=1;j<n;++j){sum[i][j] += sum[i][j-1];}}for(int i=1;i<m;++i){for(int j=0;j<n;++j){sum[i][j] += sum[i-1][j];}}for(int i=0;i<m;++i){for(int j=0;j<n;++j){if(grid[i][j]) continue;int x = i+stampHeight-1, y = j+stampWidth-1;if(x>=m || y>=n) continue;int temp = sum[x][y];if(i>0) temp -= sum[i-1][y];if(j>0) temp -= sum[x][j-1];if(i>0 && j>0) temp += sum[i-1][j-1];if(temp == 0){++diff[i][j];if(x+1<m) --diff[x+1][j];if(y+1<n) --diff[i][y+1];if(x+1<m && y+1<n) ++diff[x+1][y+1];}}}for(int i=0;i<m;++i){for(int j=1;j<n;++j){diff[i][j] += diff[i][j-1];}}for(int i=1;i<m;++i){for(int j=0;j<n;++j){diff[i][j] += diff[i-1][j];}}for(int i=0;i<m;++i){for(int j=0;j<n;++j){if(!grid[i][j] && !diff[i][j]) return false;}}return true;}
};

相关文章:

LeetCode每日一题——2132.用邮票贴满网格图

参考资料&#xff1a; 2132. 用邮票贴满网格图 - 力扣&#xff08;LeetCode&#xff09; 题目描述 给你一个 m x n 的二进制矩阵 grid &#xff0c;每个格子要么为 0 &#xff08;空&#xff09;要么为 1 &#xff08;被占据&#xff09;。 给你邮票的尺寸为 stampHeight x…...

PyQt6 表单布局Form Layout (QFormLayout)

锋哥原创的PyQt6视频教程&#xff1a; 2024版 PyQt6 Python桌面开发 视频教程(无废话版) 玩命更新中~_哔哩哔哩_bilibili2024版 PyQt6 Python桌面开发 视频教程(无废话版) 玩命更新中~共计43条视频&#xff0c;包括&#xff1a;2024版 PyQt6 Python桌面开发 视频教程(无废话版…...

Python: any()函数

在Python中&#xff0c;any函数是一个内置函数&#xff0c;它接受一个可迭代对象作为参数&#xff0c;并返回一个布尔值。当可迭代对象中至少一个元素为真&#xff08;非零、非空、非None等&#xff09;时&#xff0c;any函数返回True&#xff1b;否则&#xff0c;返回False。 …...

一些AG10K FPGA 调试的建议-Douglas

PLL AGM FPGA 在配置成功时&#xff0c;PLL 已经完成锁定&#xff0c;lock 信号已经变高&#xff1b;如果原设计中用 lock 信号输出实现系统 reset 的复位功能&#xff0c;就不能正确完成上电复位&#xff1b;同时&#xff0c;为了保证 PLL 相移的稳定&#xff0c;我们需要在 P…...

【模型量化】神经网络量化基础及代码学习总结

1 量化的介绍 量化是减少神经网络计算时间和能耗的最有效的方法之一。在神经网络量化中&#xff0c;权重和激活张量存储在比训练时通常使用的16-bit或32-bit更低的比特精度。当从32-bit降低到8-bit&#xff0c;存储张量的内存开销减少了4倍&#xff0c;矩阵乘法的计算成本则二…...

次模和K次模是多项式可解吗?

次模是多项式可解吗 **是的&#xff0c;**次模函数的最优化问题通常是多项式时间可解的。这是因为次模性质导致了问题的结构&#xff0c;使得可以利用高效的算法进行求解。 具体来说&#xff0c;针对次模函数的最优化问题&#xff0c;例如极大化或极小化这样的目标函数&#xf…...

网络安全——SQL注入实验

一、实验目的要求&#xff1a; 二、实验设备与环境&#xff1a; 三、实验原理&#xff1a; 四、实验步骤&#xff1a; 五、实验现象、结果记录及整理&#xff1a; 六、分析讨论与思考题解答&#xff1a; 七、实验截图&#xff1a; 一、实验目的要求&#xff1a; 1、…...

【cocotb】【达坦科技DatenLord】Cocotb Workshop分享

https://www.bilibili.com/video/BV19e4y1k7EE/?spm_id_from333.337.search-card.all.click&vd_sourcefd0f4be6d0a5aaa0a79d89604df3154a 方便RFM实现 cocotb_test 替代makefile &#xff0c; 类似python 函数执行...

Kafka系列之:统计kafka集群Topic的分区数和副本数,批量增加topic副本数

Kafka系列之:统计kafka集群Topic的分区数和副本数,批量增加topic副本数 一、创建KafkaAdminClient二、获取kafka集群topic元信息三、获取每个topic的名称、分区数、副本数四、生成增加topic副本的json文件五、执行增加topic副本的命令六、确认topic增加副本是否成功一、创建K…...

开具实习证明:在线实习项目介绍

大数据在线实习项目&#xff0c;是在线上为学生提供实习经验的项目。我们希望能够帮助想要在毕业后从事数据科学类工作的学生更加顺利地适应从教室到职场的转换&#xff1b;也帮助那些在工作中需要处理数据、实现数据价值的其他职能的从业者高效快速地掌握每天都能用起来的数据…...

MFC逆向之CrackMe Level3 过反调试 + 写注册机

今天我来分享一下,过反调试的方法以及使用IDA还原代码 写注册机的过程 由于内容太多,我准备分为两个帖子写,这个帖子主要是写IDA还原代码,下一个帖子是写反调试的分析以及过反调试和异常 这个CrackMe Level3是一个朋友发我的,我也不知道他在哪里弄的,我感觉挺好玩的,对反调试…...

【Centos】

一、Virtualbox安装Centos 1、Virtualbox 下载地址: Virtualbox 2、Centos 下载地址: Centos 3、Virtualbox安装Centos教程 Virtualbox安装Centos教程: Virtualbox安装Centos教程...

1+X大数据平台运维职业技能等级证书中级

hadoop&#xff1a; 由于我的功能限制&#xff0c;我无法直接为您执行这些操作或提供实际的截图。但我可以为您提供一步步的指导&#xff0c;帮助您完成这些任务。 1. 解压JDK安装包到“/usr/local/src”路径&#xff0c;并配置环境变量。 - 解压JDK&#xff1a;tar -zxf jd…...

网络基础(五):网络层协议介绍

目录 一、网络层 1、网络层的概念 2、网络层功能 3、IP数据包格式 二、ICMP协议 1、ICMP的作用和功能 2、ping命令的使用 2.1ping命令的通用格式 2.2ping命令的常用参数 2.3TypeCode&#xff1a;查看不同功能的ICMP报文 2.4ping出现问题 3、Tracert 4、冲突域 5、…...

浅显易懂 @JsonIgnore 的作用

1.JsonIgnore作用   在json序列化/反序列化时将java bean中使用了该注解的属性忽略掉 2.这个注解可以用在类/属性上   例如&#xff1a;在返回user对象时&#xff0c;在pwd属性上使用这个注解&#xff0c;返回user对象时会直接去掉pwd这个字段&#xff0c;不管这个属性有没…...

【计算机设计大赛作品】诗意千年—唐朝诗人群像的数字展现_附源码—信息可视化赛道获奖项目深入剖析【可视化项目案例-20】

🎉🎊🎉 你的技术旅程将在这里启航! 记得看本专栏里顶置的可视化宝典导航贴哦! 🚀🚀 本专栏为可视化专栏,包含现有的所有可视化技术。订阅专栏用户在文章底部可下载对应案例完整源码以供大家深入的学习研究。 🎓 每一个案例都会提供完整代码和详细的讲解,不论你…...

「Swift」Xcode多Target创建

前言&#xff1a;我们日常开发中会使用多个环境&#xff0c;如Dev、UAT&#xff0c;每个环境对应的业务功能都不同&#xff0c;但每个环境之间都只存在较小的差异&#xff0c;所以此时可以使用创建多个Target来实现&#xff0c;每个Target对应这个一个App&#xff0c;可以实现一…...

Python文件命名规则:批量重命名与规则匹配的文件

我从一个旧的 iOS 项目中获得了一个文件夹&#xff0c;其中包含许多类似于 image.png image2x.png another-image.png another-image2x.png然而&#xff0c;由于该项目现在只需要 2x.png 图像&#xff0c;我已经删除了所有的文件没有 2x 的名称。 但是我现在想知道如何轻松…...

『npm』一条命令快速配置npm淘宝国内镜像

&#x1f4e3;读完这篇文章里你能收获到 一条命令快速切换至淘宝镜像恢复官方镜像 文章目录 一、设置淘宝镜像源二、恢复官方镜像源三、查看当前使用的镜像 一、设置淘宝镜像源 npm config set registry https://registry.npm.taobao.org服务器建议全局设置 sudo npm config…...

Java EE 多线程之线程安全的集合类

文章目录 1. 多线程环境使用 ArrayList1. 1 Collections.synchronizedList(new ArrayList)1.2 CopyOnWriteArrayList 2. 多线程环境使用队列2.1 ArrayBlockingQueue2.2 LinkedBlockingQueue2.3 PriorityBlockingQueue2.4 TransferQueue 3. 多线程环境使用哈希表3.1 Hashtable3.…...

接口测试中缓存处理策略

在接口测试中&#xff0c;缓存处理策略是一个关键环节&#xff0c;直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性&#xff0c;避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明&#xff1a; 一、缓存处理的核…...

基于FPGA的PID算法学习———实现PID比例控制算法

基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容&#xff1a;参考网站&#xff1a; PID算法控制 PID即&#xff1a;Proportional&#xff08;比例&#xff09;、Integral&#xff08;积分&…...

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

Qt Widget类解析与代码注释

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码&#xff0c;写上注释 当然可以&#xff01;这段代码是 Qt …...

转转集团旗下首家二手多品类循环仓店“超级转转”开业

6月9日&#xff0c;国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解&#xff0c;“超级…...

对WWDC 2025 Keynote 内容的预测

借助我们以往对苹果公司发展路径的深入研究经验&#xff0c;以及大语言模型的分析能力&#xff0c;我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际&#xff0c;我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测&#xff0c;聊作存档。等到明…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

vue3 定时器-定义全局方法 vue+ts

1.创建ts文件 路径&#xff1a;src/utils/timer.ts 完整代码&#xff1a; import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...

MySQL中【正则表达式】用法

MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现&#xff08;两者等价&#xff09;&#xff0c;用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例&#xff1a; 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...