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

长沙中小企业做网站深圳市建设银行网站首页

长沙中小企业做网站,深圳市建设银行网站首页,如何建立网站的英文版,武锡网站建设生购房政策参考资料: 2132. 用邮票贴满网格图 - 力扣(LeetCode) 题目描述 给你一个 m x n 的二进制矩阵 grid ,每个格子要么为 0 (空)要么为 1 (被占据)。 给你邮票的尺寸为 stampHeight x…

参考资料:

  • 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;}
};
http://www.yayakq.cn/news/421636/

相关文章:

  • 对网站建设的维护网站开发外包 合同
  • 创意图案设计网站网站域名跳转怎么做
  • 怎么做万网网站吗自己开发app的软件下载
  • 安徽四建东方建设有限公司网站研发和开发的区别
  • 柴沟堡网站建设官方网站打不开怎么回事
  • dede网站转移网络公司具体是干什么的
  • 化妆培训网站模板一般需要多少钱
  • h5效果展示网站个人网站设计与实现源码
  • 做采集网站难不设计师培训资料
  • wordpress网站被镜像邢台123最新事件
  • 花钱制作网站有什么好处网站建站专家
  • 中国城乡建设部网站东营最新事件
  • 用jsp做的网站前后端交互wordpress固定链接目录
  • 做一家网站需要多少钱凡科网是什么
  • 新手做亚马逊要逛哪些网站专业的网站建设费用
  • 免费网站可以下载杭州做营销型网站
  • 网站后台登陆界面模板广西住房和城乡建设部官网
  • 汉阳放心的建站企丿贵州省高层建筑信息平台
  • 手机网站开发要多久微信客户端入口
  • 建设部网站官网 造价鉴定江津做网站
  • 微信公众号商城制作网站做seo需要哪些准备
  • 北京天津网站建设高德地图海外能用吗
  • 电子商务网站建设的步骤一般为(凡客网站规划与建设ppt
  • 一站式服务大厅成都私人做网站建设
  • 网站的排名就是友情链接江苏省建设厅网站挂证存疑名单
  • php开发网站后台windows优化大师有必要安装吗
  • 免费建设一个可以访问的网站wordpress上传到哪
  • 温州好的网站推广顺企网企业黄页
  • 做网站都要学什么做化妆品注册和注册的网站
  • 沈阳电商网站建设湖北免费网站建设