南充网站建设网站,爬知乎文章做网站,html in wordpress,漳州网站设计制作参考资料#xff1a;
2132. 用邮票贴满网格图 - 力扣#xff08;LeetCode#xff09;
题目描述
给你一个 m x n 的二进制矩阵 grid #xff0c;每个格子要么为 0 #xff08;空#xff09;要么为 1 #xff08;被占据#xff09;。
给你邮票的尺寸为 stampHeight x…参考资料
2132. 用邮票贴满网格图 - 力扣LeetCode
题目描述
给你一个 m x n 的二进制矩阵 grid 每个格子要么为 0 空要么为 1 被占据。
给你邮票的尺寸为 stampHeight x stampWidth 。我们想将邮票贴进二进制矩阵中且满足以下 限制 和 要求
覆盖所有 空 格子。不覆盖任何 被占据 的格子。我们可以放入任意数目的邮票。邮票可以相互有 重叠 部分。邮票不允许 旋转 。邮票必须完全在矩阵 内 。
如果在满足上述要求的前提下可以放入邮票请返回 true 否则返回 false 。
样例 思路
主要思想二维前缀和 二维差分
由于题目没有限制放入邮票的数量也允许邮票相互重叠所以我们应该尽可能地多贴邮票。
假设我们以邮票的左上角 (i,j)为基准粘贴邮票则该邮票的覆盖范围是 (i.j) ~ (x,y) 其中 x istampHeight-1, y jstampHeight-1。为了铺满整张网格图我们遍历每个格子判断能否以当前格子为左上角粘贴邮票最后我们检查是否每个空格子都被邮票覆盖即可。关键问题在于
如果快速判断一个矩形范围 (i.j) ~ (x,y) 内是否存在被占据的格子。在贴上邮票后如何更新矩阵的状态并在最后快速判断每个空格子是否被覆盖。
对于第一个问题我们可以使用二维前缀和解决。定义 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 就应该按照下图方式修改 代码 不得不承认我求二维前缀和、二维差分的代码极其丑陋。。。 class Solution {
public:bool possibleToStamp(vectorvectorint grid, int stampHeight, int stampWidth) {int m grid.size(), n grid[0].size();vectorvectorint sum(grid.begin(), grid.end());vectorvectorint diff(m, vectorint(n, 0));for(int i0;im;i){for(int j1;jn;j){sum[i][j] sum[i][j-1];}}for(int i1;im;i){for(int j0;jn;j){sum[i][j] sum[i-1][j];}}for(int i0;im;i){for(int j0;jn;j){if(grid[i][j]) continue;int x istampHeight-1, y jstampWidth-1;if(xm || yn) continue;int temp sum[x][y];if(i0) temp - sum[i-1][y];if(j0) temp - sum[x][j-1];if(i0 j0) temp sum[i-1][j-1];if(temp 0){diff[i][j];if(x1m) --diff[x1][j];if(y1n) --diff[i][y1];if(x1m y1n) diff[x1][y1];}}}for(int i0;im;i){for(int j1;jn;j){diff[i][j] diff[i][j-1];}}for(int i1;im;i){for(int j0;jn;j){diff[i][j] diff[i-1][j];}}for(int i0;im;i){for(int j0;jn;j){if(!grid[i][j] !diff[i][j]) return false;}}return true;}
};
