C++前缀和算法的应用:用地毯覆盖后的最少白色砖块 原理源码测试用例

简介: C++前缀和算法的应用:用地毯覆盖后的最少白色砖块 原理源码测试用例

本文涉及的基础知识点

C++算法:前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频

题目

给你一个下标从 0 开始的 二进制 字符串 floor ,它表示地板上砖块的颜色。

floor[i] = ‘0’ 表示地板上第 i 块砖块的颜色是 黑色 。

floor[i] = ‘1’ 表示地板上第 i 块砖块的颜色是 白色 。

同时给你 numCarpets 和 carpetLen 。你有 numCarpets 条 黑色 的地毯,每一条 黑色 的地毯长度都为 carpetLen 块砖块。请你使用这些地毯去覆盖砖块,使得未被覆盖的剩余 白色 砖块的数目 最小 。地毯相互之间可以覆盖。

请你返回没被覆盖的白色砖块的 最少 数目。

示例 1:

输入:floor = “10110101”, numCarpets = 2, carpetLen = 2

输出:2

解释:

上图展示了剩余 2 块白色砖块的方案。

没有其他方案可以使未被覆盖的白色砖块少于 2 块。

示例 2:

输入:floor = “11111”, numCarpets = 2, carpetLen = 3

输出:0

解释:

上图展示了所有白色砖块都被覆盖的一种方案。

注意,地毯相互之间可以覆盖。

参数范围:

1 <= carpetLen <= floor.length <= 1000

floor[i] 要么是 ‘0’ ,要么是 ‘1’ 。

1 <= numCarpets <= 1000

分析

原理

毛毯尽量不相互覆盖,这样可以覆盖更多的白砖。除非:毛毯放不下了。

如果能够覆盖一张毛毯,那么一定可以覆盖无限毛毯。除非 floor.length 小于carpetLen,否则一定可以覆盖。这种情况题目已经排除了。

计算最多可以盖住多少块白砖,白砖数减去盖住的白砖,就是未盖住的白砖数。

假定新毯子覆盖在[iPre,iPre + carpetLen),那么前一张毯子不一定在[iPre-carpetLen,iPre),可以更前。所以执行:

dp[i + 1] = max(dp[i], dp[i + 1]);

执行之前:dp[i]的含义是i的最后一张毯子的尾部,可以覆盖最多砖瓦数。

执行之后:dp[i]的含义是的最后一张毯子的尾部<=i,可以覆盖最多砖瓦数。

时间复杂度

O(n*n)。两层循环,第一层,枚举第i张毛毯。第二层循环,枚举上一次的覆盖位置。

步骤

一,计算白砖数量的前缀和。

二,两层循环。

## 变量解释

vSum vSum[i]表示 floor[0,i)中白砖的数量,也就是前i块砖中,白砖的数量
pre 表示i块毯子,覆盖了[0,i),能盖住的最多白砖数

代码

核心代码

class Solution {
public:
int minimumWhiteTiles(string floor, int numCarpets, int carpetLen) {
//错误想法:如果盖毯子,则毯子的末端一定盖住白砖
//计算最多可以盖住多少块白砖
vector vSum = { 0 };//vSum[i]表示 floor[0,i)中白砖的数量
for (const char& ch : floor)
{
vSum.emplace_back(vSum.back() + (‘1’ == ch));
}
m_c = floor.length();
vector pre (m_c+1,0);//表示i块毯子,覆盖了[0,i),能盖住的最多白砖数
for (int i = 0; i < numCarpets; i++)
{
vector dp = pre;
for (int iPre = 0; iPre < pre.size(); iPre++)
{
const int iNew = min(m_c , iPre + carpetLen);
dp[iNew] = max(dp[iNew], pre[iPre] + (vSum[iNew]-vSum[iPre]));
}
for (int i = 0; i < m_c; i++)
{
dp[i + 1] = max(dp[i], dp[i + 1]);
}
pre.swap(dp);
}
return vSum.back() - *std::max_element(pre.begin(),pre.end());
}
int m_c;
};

测试用例

template
void Assert(const vector& v1, const vector& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
assert(v1[i] == v2[i]);
}
}
template
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}
int main()
{
Solution slu;
string floor = “10110101”;
int numCarpets = 2, carpetLen = 2;
int res;
floor = "1110111";
numCarpets = 2, carpetLen = 3;
res = slu.minimumWhiteTiles(floor, numCarpets, carpetLen);
Assert(0, res);
floor = "10110101";
numCarpets = 2, carpetLen = 2;
res = slu.minimumWhiteTiles(floor, numCarpets, carpetLen);
Assert(2, res);
floor = "11111";
numCarpets = 2, carpetLen = 3;
res = slu.minimumWhiteTiles(floor, numCarpets, carpetLen);
Assert(0, res); 
//CConsole::Out(res);

}

2023年2月旧代码

class Solution {
public:
int minimumWhiteTiles(const string floor, const int numCarpets, const int carpetLen) {
m_c = floor.length();
//dp[i][j] 已经处理了i块砖,用了j块地毯,最少为覆盖的砖数
vector<vector> dp(m_c+1, vector(numCarpets+1,INT_MAX));
dp[0][0] = 0;
for (int brick = 0; brick < m_c; brick++)
{
for (int iUseCarpets = 0; iUseCarpets <= numCarpets; iUseCarpets++)
{
const int& iValue = dp[brick][iUseCarpets];
if (INT_MAX == iValue)
{
continue;
}
//空一格
dp[brick + 1][iUseCarpets] = min(dp[brick + 1][iUseCarpets], iValue + (‘1’ == floor[brick]));
//假定不重叠,如果重叠右移到不重叠,不影响结果
if (numCarpets == iUseCarpets)
{
continue;
}
const int iNewBrick = min(brick + carpetLen, m_c);
dp[iNewBrick][iUseCarpets + 1] = min(dp[iNewBrick][iUseCarpets + 1], iValue);
}
}
return *std::min_element(dp[m_c].begin(), dp[m_c].end());
}
int m_c;
};

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。

https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程

https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法,请下载《闻缺陷则喜算法册》doc版

https://download.csdn.net/download/he_zhidan/88348653

| 鄙人想对大家说的话

|

|-|

|闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。|

| 墨家名称的来源:有所得以墨记之。 |

|如果程序是一条龙,那算法就是他的是睛|

测试环境

操作系统:win7 开发环境: VS2019 C++17

或者 操作系统:win10 开发环境:

VS2022 C++17

相关文章
|
4天前
|
机器学习/深度学习 敏捷开发 存储
深入理解自动化测试中的数据驱动策略深度学习在图像识别中的应用与挑战
【5月更文挑战第20天】 在现代软件开发过程中,自动化测试已成为确保产品质量和加快市场投放速度的关键因素。数据驱动测试(DDT)作为一种高效的自动化测试策略,它允许测试用例与测试数据分离,从而增强测试案例的可重用性并提高测试覆盖率。本文将探讨数据驱动策略的核心概念、实现方法以及在实际测试中的应用,旨在为软件测试工程师提供一种系统化和模块化的测试手段。 【5月更文挑战第20天】 随着人工智能技术的飞速发展,深度学习已经成为了图像识别领域的核心技术。本文将探讨深度学习在图像识别中的应用,以及在实际应用中所面临的挑战。我们将介绍卷积神经网络(CNN)的基本概念,以及如何利用深度学习进行图像分类、目
|
5天前
|
算法 Java
并发垃圾回收算法对于大规模服务器应用的优势
并发垃圾回收算法对于大规模服务器应用的优势
|
1天前
|
敏捷开发 机器学习/深度学习 人工智能
探索自动化测试在敏捷开发中的应用与挑战
【5月更文挑战第23天】 随着软件开发实践的不断演进,敏捷开发已成为多数团队的首选模式。在此背景下,自动化测试作为确保软件质量和快速响应变化的关键手段,其角色愈发重要。本文将深入探讨自动化测试在敏捷环境下的应用实践,分析其在持续集成和交付过程中的作用,并讨论面临的主要挑战及可能的解决方案。通过实际案例分析和最新技术趋势的梳理,旨在为读者提供对自动化测试深层次理解的同时,指出未来发展方向。
|
1天前
|
敏捷开发 IDE 测试技术
深入探索自动化测试工具Selenium的高效应用
【5月更文挑战第23天】 在快速演进的数字时代,软件开发周期不断缩短,而质量保证的需求却日益增加。自动化测试作为确保软件质量的关键手段之一,其重要性不言而喻。Selenium作为一种广泛使用的自动化测试工具,因其跨平台、多语言支持和开源等特性,在业界得到了广泛应用。本文将深入分析Selenium的核心功能,探讨其在真实项目中的应用策略,并通过案例分析展示如何通过Selenium提高测试效率和准确性。
|
1天前
|
Java 测试技术 持续交付
深入理解与应用软件自动化测试框架
【5月更文挑战第23天】 随着软件开发周期的不断缩短和发布频率的加快,传统的手动测试方法已难以满足快速迭代的需求。因此,本文将深入探讨自动化测试在现代软件开发中的关键作用,特别是自动化测试框架的设计与实现。文章首先回顾了自动化测试的基本概念和核心优势,接着详细分析了几种流行的自动化测试框架(如Selenium、Appium和JUnit)的特点及应用场景。然后,重点讨论了如何根据项目需求选择适合的测试框架,以及如何构建一个可靠且易于维护的自动化测试环境。最后,通过实际案例分析,展示了自动化测试框架在提高测试效率和确保软件质量方面的实践成效。
|
4天前
|
敏捷开发 Devops jenkins
深入理解与实践:持续集成在软件测试中的应用
【5月更文挑战第20天】 随着敏捷开发和DevOps文化的普及,持续集成(Continuous Integration, CI)已成为软件开发周期中不可或缺的一环。本文将探讨CI在软件测试中的关键作用,包括其如何提高测试效率、减少集成问题以及促进团队协作。通过分析持续集成的工作流程和工具使用,我们将展示如何在现代软件工程实践中有效地整合CI策略,以确保代码质量和项目稳定性。
|
9天前
|
算法 数据安全/隐私保护 计算机视觉
基于二维CS-SCHT变换和LABS方法的水印嵌入和提取算法matlab仿真
该内容包括一个算法的运行展示和详细步骤,使用了MATLAB2022a。算法涉及水印嵌入和提取,利用LAB色彩空间可能用于隐藏水印。水印通过二维CS-SCHT变换、低频系数处理和特定解码策略来提取。代码段展示了水印置乱、图像处理(如噪声、旋转、剪切等攻击)以及水印的逆置乱和提取过程。最后,计算并保存了比特率,用于评估水印的稳健性。
|
2天前
|
机器学习/深度学习 算法
基于BP神经网络的QPSK解调算法matlab性能仿真
该文介绍了使用MATLAB2022a实现的QPSK信号BP神经网络解调算法。QPSK调制信号在复杂信道环境下受到干扰,BP网络能适应性地补偿失真,降低误码率。核心程序涉及数据分割、网络训练及性能评估,最终通过星座图和误码率曲线展示结果。
|
3天前
|
机器学习/深度学习 算法 计算机视觉
基于yolov2深度学习网络模型的鱼眼镜头中人员检测算法matlab仿真
该内容是一个关于基于YOLOv2的鱼眼镜头人员检测算法的介绍。展示了算法运行的三张效果图,使用的是matlab2022a软件。YOLOv2模型结合鱼眼镜头畸变校正技术,对鱼眼图像中的人员进行准确检测。算法流程包括图像预处理、网络前向传播、边界框预测与分类及后处理。核心程序段加载预训练的YOLOv2检测器,遍历并处理图像,检测到的目标用矩形标注显示。
|
6天前
|
算法
m基于BP译码算法的LDPC编译码matlab误码率仿真,对比不同的码长
MATLAB 2022a仿真实现了LDPC码的性能分析,展示了不同码长对纠错能力的影响。短码长LDPC码收敛快但纠错能力有限,长码长则提供更强纠错能力但易陷入局部最优。核心代码通过循环进行误码率仿真,根据EsN0计算误比特率,并保存不同码长(12-768)的结果数据。
26 9
m基于BP译码算法的LDPC编译码matlab误码率仿真,对比不同的码长