江门网站建设开发,网站后台一般是用什么做的,注册了域名怎么添加到自己的网站,旧房装修找哪家【LetMeFly】2132.用邮票贴满网格图#xff1a;二维前缀和 二维差分
力扣题目链接#xff1a;https://leetcode.cn/problems/stamping-the-grid/
给你一个 m x n 的二进制矩阵 grid #xff0c;每个格子要么为 0 #xff08;空#xff09;要么为 1 #xff08;被占据二维前缀和 二维差分
力扣题目链接https://leetcode.cn/problems/stamping-the-grid/
给你一个 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.lengthn grid[r].length1 m, n 1051 m * n 2 * 105grid[r][c] 要么是 0 要么是 1 。1 stampHeight, stampWidth 105
方法一二维前缀和 二维差分
二维前缀和预处理好后可以在 O ( 1 ) O(1) O(1)的时间内查出任意矩形的所有元素之和。 p r e f i x [ i 1 ] [ j 1 ] prefix[i 1][j 1] prefix[i1][j1]是 m a t [ i ] [ j ] mat[i][j] mat[i][j]及其左上角所有元素组成的矩阵的和
若矩形内每个元素都加d则可以在 O ( 1 ) O(1) O(1)的时间内记录到差分数组中。最后能以 O ( m n ) O(mn) O(mn)的时间还原出原数组。按求前缀和的方式对差分数组计算即可得到原矩阵
因为贴邮票的次数不限因此我们决定能贴的下就贴。最后看看是否还有空格即可。
具体思路
消耗 O ( m n ) O(mn) O(mn)的时间计算出前缀和数组。
遍历矩阵中的每个空白位置若以这个位置为左上角可以贴邮票通过前缀和能很快确认则贴邮票通过差分数组能很快记录。
最终再消耗 O ( m n ) O(mn) O(mn)的时间还原出贴发票后的矩阵。
时间复杂度 O ( s i z e ( g r i d ) ) O(size(grid)) O(size(grid))空间复杂度 O ( s i z e ( g r i d ) ) O(size(grid)) O(size(grid))
AC代码
C
class Solution {
public:bool possibleToStamp(vectorvectorint grid, int h, int w) {int n grid.size(), m grid[0].size();vectorvectorint prefix(n 1, vectorint(m 1)), diff(n 2, vectorint(m 2));// prefixfor (int i 0; i n; i) {for (int j 0; j m; j) {prefix[i 1][j 1] grid[i][j] prefix[i][j 1] prefix[i 1][j] - prefix[i][j];}}// stampfor (int i 0; i h - 1 n; i) {for (int j 0; j w - 1 m; j) {// (i, j) - (i h - 1, j w - 1)if (!grid[i][j] !(prefix[i h][j w] - prefix[i h][j] - prefix[i][j w] prefix[i][j])) {diff[i 1][j 1];diff[i 1][j w 1]--;diff[i h 1][j 1]--;diff[i h 1][j w 1];}}}// un-difffor (int i 0; i n; i) {for (int j 0; j m; j) {diff[i 1][j 1] diff[i][j 1] diff[i 1][j] - diff[i][j];if (!grid[i][j] !diff[i 1][j 1]) {return false;}}}return true;}
};Python
# from typing import Listclass Solution:def possibleToStamp(self, grid: List[List[int]], h: int, w: int) - bool:n, m len(grid), len(grid[0])prefix [[0] * (m 1) for _ in range(n 1)]diff [[0] * (m 2) for _ in range(n 2)]# get-prefixfor i in range(n):for j in range(m):prefix[i 1][j 1] grid[i][j] prefix[i 1][j] prefix[i][j 1] - prefix[i][j]# stampfor i in range(n - h 1):for j in range(m - w 1):# (i, j) - (i h - 1, j w - 1)if not grid[i][j] and not (prefix[i h][j w] prefix[i][j] - prefix[i h][j] - prefix[i][j w]):diff[i 1][j 1] 1diff[i h 1][j 1] - 1diff[i 1][j w 1] - 1diff[i h 1][j w 1] 1# un-difffor i in range(n):for j in range(m):diff[i 1][j 1] diff[i 1][j] diff[i][j 1] - diff[i][j]if not grid[i][j] and not diff[i 1][j 1]:return Falsereturn True同步发文于CSDN原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/135002925
