阿里云做的网站怎么备份,163企业邮箱注册入口,php响应式个人博客网站设计,公众号怎么制作流程本文涉及知识点
二维差分
LeetCode2132. 用邮票贴满网格图
给你一个 m x n 的二进制矩阵 grid #xff0c;每个格子要么为 0 #xff08;空#xff09;要么为 1 #xff08;被占据#xff09;。 给你邮票的尺寸为 stampHeight x stampWidth 。我们想将邮票贴进二进制矩…本文涉及知识点
二维差分
LeetCode2132. 用邮票贴满网格图
给你一个 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 105 1 m * n 2 * 105 grid[r][c] 要么是 0 要么是 1 。 1 stampHeight, stampWidth 105
二维差分
邮票无限且可以相互覆盖能成为邮票左上角的位置都放一张。 邮票的左上角能否放到(r,c)则称(r,c)能否放置邮票。 两轮二维差分 一vDiff1记录那些位置可以放邮票。 二vDiff2记录那些位置已经放置了邮票或被占据。 具体 一如果(r,c)被占据则左上角(r-stampHeight1,c - stampWidth1)右下角为(r,c)的矩形无法放置邮票。左上角不能为负数。 二ans1 vDif1的结果。 三从0到大枚举r直到rstampHeightm不成立。从0到大枚举c直到cstampWidthn不成立。 ,如果vDiff[r][c]等于0,则放置邮票到vDiff2。 四r 0 to m-1 ,c 0 to n-1如果grid[r][c]1则vDiff.set(r,c,r1,c1) 五ans2 vDiff2的结果。 六r 0 to m-1 ,c 0 to n-1如果res2[r][c]等于0返回fasle。 七return true; 一四可以合并。
代码
核心代码
templateclass T int
class CDiff2
{
public:CDiff2(int r, int c) :m_iR(r), m_iC(c) {m_vDiff.assign(m_iR, vectorT(m_iC));}void Set(int r1, int c1, int r2Exinc, int c2Exinc, int iAdd) {m_vDiff[r1][c1] iAdd;m_vDiff[r2Exinc][c2Exinc] iAdd;m_vDiff[r1][c2Exinc] - iAdd;m_vDiff[r2Exinc][c1] - iAdd;}vectorvectorT Ans()const {vectorvectorT res(m_iR, vectorT(m_iC));vectorT vCols(m_iC);for (int r 0; r m_iR; r) {T iSum 0;for (int c 0; c m_iC; c) {vCols[c] m_vDiff[r][c];iSum vCols[c];res[r][c] iSum;}}return res;}const int m_iR, m_iC;
protected:vectorvectorT m_vDiff;
};class Solution {
public:bool possibleToStamp(vectorvectorint grid, int stampHeight, int stampWidth) {const int R grid.size();const int C grid[0].size();CDiff2 diff1(R 1, C 1), diff2(R 1, C 1);for (int r 0; r R; r) {for (int c 0; c C; c) {if (0 grid[r][c]) { continue; }diff1.Set(max(0, r - stampHeight 1), max(0, c - stampWidth 1), r 1, c 1, 1);diff2.Set(r, c, r 1, c 1, 1); }}auto ans1 diff1.Ans();for (int r 0; r stampHeight R; r) {for (int c 0; c stampWidth C; c) {if (0 ans1[r][c]) {diff2.Set(r, c, r stampHeight, c stampWidth, 1);}}}auto ans2 diff2.Ans();for (int r 0; r R; r) {for (int c 0; c C; c) {if (0ans2[r][c] ) { return false; }}}return true;}
};单元测试
templateclass T1,class T2
void AssertEx(const T1 t1, const T2 t2)
{Assert::AreEqual(t1 , t2);
}templateclass T
void AssertEx(const vectorT v1, const vectorT v2)
{Assert::AreEqual(v1.size(), v2.size()); for (int i 0; i v1.size(); i){Assert::AreEqual(v1[i], v2[i]);}
}templateclass T
void AssertV2(vectorvectorT vv1, vectorvectorT vv2)
{sort(vv1.begin(), vv1.end());sort(vv2.begin(), vv2.end());Assert::AreEqual(vv1.size(), vv2.size());for (int i 0; i vv1.size(); i){AssertEx(vv1[i], vv2[i]);}
}namespace UnitTest
{vectorvectorint grid;int stampHeight, stampWidth;TEST_CLASS(UnitTest){public:TEST_METHOD(TestMethod0){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;auto res Solution().possibleToStamp(grid, stampHeight, stampWidth);AssertEx( true, res);}TEST_METHOD(TestMethod1){grid { {1,0,0,0},{0,1,0,0},{0,0,1,0},{0,0,0,1} }, stampHeight 2, stampWidth 2;auto res Solution().possibleToStamp(grid, stampHeight, stampWidth);AssertEx(false, res);}};
} 扩展阅读
视频课程
先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。 https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176
相关推荐
我想对大家说的话《喜缺全书算法册》以原理、正确性证明、总结为主。按类别查阅鄙人的算法文章请点击《算法与数据汇总》。有效学习明确的目标 及时的反馈 拉伸区难度合适 专注闻缺陷则喜是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
