Basic knowledge points involved in this article
C++ algorithm: principles, source code and test cases of prefix sum, prefix product, prefix XOR including course videos
Title
You are given a binary string floor whose index starts from 0, which represents the color of the bricks on the floor.
floor[i] = 0’ means that the color of the i-th brick on the floor is black.
floor[i] = 1’ means that the color of the i-th brick on the floor is white.
Giving you both numCarpets and carpetLen . You have numCarpets black carpets, each black carpet is carpetLen bricks long. Please use these carpets to cover the bricks so that the number of remaining white bricks that are not covered is minimized. Carpets can cover each other.
Please return the minimum number of uncovered white bricks.
Example 1:
Input: floor = “10110101”, numCarpets = 2, carpetLen = 2
Output: 2
explain:
The picture above shows the plan for the remaining 2 white bricks.
There is no alternative that leaves less than 2 uncovered white bricks.
Example 2:
Input: floor = “11111”, numCarpets = 2, carpetLen = 3
Output: 0
explain:
The picture above shows a scheme where all the white bricks are covered.
Note that carpets can cover each other.
Parameter range:
1 <= carpetLen <= floor.length <= 1000
floor[i] is either 0’ or 1’ .
1 <= numCarpets <= 1000
Analysis
Principle
Try not to cover each other with blankets so that more white bricks can be covered. Unless: the blanket won’t fit.
If you can cover one blanket, you can certainly cover infinite blankets. Unless floor.length is less than carpetLen, it can be overwritten. This situation has been eliminated.
Calculate the maximum number of white bricks that can be covered. The number of white bricks minus the covered white bricks is the number of uncovered white bricks.
Assuming that the new blanket is covered in [iPre, iPre + carpetLen), then the previous blanket is not necessarily in [iPre-carpetLen, iPre) and can be moved forward. So execute:
dp[i + 1] = max(dp[i], dp[i + 1]);
Before execution: The meaning of dp[i] is the tail of the last blanket of i, which can cover the maximum number of bricks.
After execution: The meaning of dp[i] is that the tail of the last blanket <=i can cover the maximum number of bricks.
Time complexity
O(n*n). Two-layer loop, the first layer enumerates the i-th blanket. The second level of loop enumerates the last covered position.
Steps
1. Calculate the prefix sum of the number of white bricks.
Second, two layers of circulation.
## Variable explanation
| vSum | vSum[ i] represents the number of white bricks in floor[0,i), that is, the number of white bricks in the first i bricks |
| pre | represents i blanket covers [0,i), the maximum number of white bricks that can be covered |
Code
Core code
class Solution {
public:
int minimumWhiteTiles(string floor, int numCarpets, int carpetLen) {
//Wrong idea: If you cover a blanket, the end of the blanket must cover the white bricks
//Calculate the maximum number of white bricks that can be covered
vector vSum = { 0 }; //vSum[i] represents the number of white bricks in 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);//Indicates i blanket, covering [0,i), the maximum number of white bricks that can be covered
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;
};
Test cases
template
void Assert(const vector & amp; v1, const vector & amp; 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 slug;
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);
}
Old code in February 2023
class Solution {
public:
int minimumWhiteTiles(const string floor, const int numCarpets, const int carpetLen) {
m_c = floor.length();
//dp[i][j] has processed i bricks and used j carpets. The minimum number of bricks covered is
vector
dp[0][0] = 0;
for (int brick = 0; brick < m_c; brick + + )
{
for (int iUseCarpets = 0; iUseCarpets <= numCarpets; iUseCarpets + + )
{
const int & amp; iValue = dp[brick][iUseCarpets];
if (INT_MAX == iValue)
{
continue;
}
//Empty space
dp[brick + 1][iUseCarpets] = min(dp[brick + 1][iUseCarpets], iValue + (1’ == floor[brick]));
//Assume no overlap. If the overlap is moved to the right and does not overlap, the result will not be affected.
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;
};
Extended reading
Video course
Effective learning: clear goals, timely feedback, stretching zone (appropriate difficulty), you can learn simple courses first, please go to CSDN Academy and listen to the explanation of Baiyin Lecturer (that is, I).
https://edu.csdn.net/course/detail/38771
how fast do you want
A battle has quickly formed. To share the worries of your boss, please learn C# onboarding training, C++ onboarding training and other courses.
https://edu.csdn.net/lecturer/6176
Related downloads
If you want to know the superior learning algorithm, please download the doc version of “Algorithm Book When You Hear the Defects”
https://download.csdn.net/download/he_zhidan/88348653
| What I want to say to you all
|
|-|
|Rejoicing when you hear defects is a good wish, to find problems early, correct them early, and save money for the boss. |
| The origin of the Mohist name: Everything is recorded in Mohism. |
|If the program is a dragon, then the algorithm is his key point|
Test environment
Operating system: win7 Development environment: VS2019 C++ 17
Or operating system: win10 development environment:
VS2022 C++ 17
