建设一个网站需要哪些费用,申请建设部门网站的报告,百度网盘下载的文件在哪,品牌传播方案文章目录1. 题目2. 解题1. 题目
给你一个 m x n 的二进制矩阵 grid #xff0c;每个格子要么为 0 #xff08;空#xff09;要么为 1 #xff08;被占据#xff09;。
给你邮票的尺寸为 stampHeight x stampWidth 。我们想将邮票贴进二进制矩阵中#xff0c;且满足以下…
文章目录1. 题目2. 解题1. 题目
给你一个 m x n 的二进制矩阵 grid 每个格子要么为 0 空要么为 1 被占据。
给你邮票的尺寸为 stampHeight x stampWidth 。我们想将邮票贴进二进制矩阵中且满足以下 限制 和 要求
覆盖所有 空 格子。不覆盖任何 被占据 的格子。我们可以放入任意数目的邮票。邮票可以相互有 重叠 部分。邮票不允许 旋转 。邮票必须完全在矩阵 内 。
如果在满足上述要求的前提下可以放入邮票请返回 true 否则返回 false 。
示例 1
输入grid [[1,0,0,0],[1,0,0,0],[1,0,0,0],[1,0,0,0],[1,0,0,0]],
stampHeight 4, stampWidth 3
输出true
解释我们放入两个有重叠部分的邮票图中标号为 1 和 2它们能覆盖所有与空格子。示例 2
输入grid [[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]],
stampHeight 2, stampWidth 2
输出false
解释没办法放入邮票覆盖所有的空格子且邮票不超出网格图以外。提示
m grid.length
n grid[r].length
1 m, n 10^5
1 m * n 2 * 10^5
grid[r][c] 要么是 0 要么是 1 。
1 stampHeight, stampWidth 10^5来源力扣LeetCode 链接https://leetcode-cn.com/problems/stamping-the-grid 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
DP 的方法求矩形区域内的 1 的数量如果 邮票区域内的 1 的数量为 0则用差分方法看的题解区做法记录这个区域访问过左上角、右下角1另外两角 -1再最后DP求差分的二维前缀和前缀和为0则该位置没有被访问过
class Solution {
public:bool possibleToStamp(vectorvectorint grid, int stampHeight, int stampWidth) {int m grid.size(), n grid[0].size();vectorvectorint dp(m1, vectorint(n1, 0));vectorvectorint diff(m2, vectorint(n2, 0));for(int i 0; i m; i){for(int j 0; j n; j){if(grid[i][j])dp[i1][j1] 1dp[i][j1]dp[i1][j]-dp[i][j];elsedp[i1][j1] dp[i][j1]dp[i1][j]-dp[i][j];}} // 求 区域内 1 的数量for(int i 0; i m; i){for(int j 0; j n; j){if(grid[i][j] || istampHeight m || jstampWidth n) continue;int outsidearea dp[istampHeight][j]dp[i][jstampWidth]-dp[i][j];// i, j 处为左上角开始贴邮票邮票之外的 1 的数量int allarea dp[istampHeight][jstampWidth];// 邮票右下角到地图左上角的 1 的数量if(allarea outsidearea) // 邮票区域内 没有 1可以贴{diff[i1][j1] 1; // 差分法记录 该区域的访问情况diff[i1][jstampWidth1] - 1;diff[istampHeight1][j1] - 1;diff[istampHeight1][jstampWidth1] 1;}}}for(int i 0; i m; i){for(int j 0; j n; j){diff[i1][j1] diff[i1][j]diff[i][j1]-diff[i][j];// 差分的二维前缀和if(grid[i][j]0 diff[i1][j1]0) return false;// 没有 1 且 没有被邮票访问过不能贴满}}return true;}
};452 ms 178.5 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
