本文涉及知识点
二维差分
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-stampHeight+1,c - stampWidth+1),右下角为(r,c)的矩形无法放置邮票。左上角不能为负数。
二,ans1 = vDif1的结果。
三,从0到大枚举r,直到r+stampHeight<=m不成立。从0到大枚举c,直到c+stampWidth<=n不成立。
,如果vDiff[r][c]等于0,则放置邮票到vDiff2。
四,r = 0 to m-1 ,c = 0 to n-1,如果grid[r][c]=1,则vDiff.set(r,c,r+1,c+1)
五,ans2 = vDiff2的结果。
六,r = 0 to m-1 ,c = 0 to n-1,如果res2[r][c]等于0,返回fasle。
七,return true;
一四可以合并。
代码
核心代码
template<class T = int >
class CDiff2
{
public:
CDiff2(int r, int c) :m_iR(r), m_iC(c) {
m_vDiff.assign(m_iR, vector<T>(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;
}
vector<vector<T>> Ans()const {
vector<vector<T>> res(m_iR, vector<T>(m_iC));
vector<T> 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:
vector<vector<T>> m_vDiff;
};
class Solution {
public:
bool possibleToStamp(vector<vector<int>>& 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 (0==ans2[r][c] ) { return false; }
}
}
return true;
}
};
单元测试
template<class T1,class T2>
void AssertEx(const T1& t1, const T2& t2)
{
Assert::AreEqual(t1 , t2);
}
template<class T>
void AssertEx(const vector<T>& v1, const vector<T>& v2)
{
Assert::AreEqual(v1.size(), v2.size());
for (int i = 0; i < v1.size(); i++)
{
Assert::AreEqual(v1[i], v2[i]);
}
}
template<class T>
void AssertV2(vector<vector<T>> vv1, vector<vector<T>> 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
{
vector<vector<int>> 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 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。