使字符串成为由一串0后面跟着一串1组成的最小移除次数

问题“进行 0 子字符串的字符串连接的最小删除量”涉及操作字符串的工作。提供 0 和 1 的字符串作为输入，结果是一个整数，反映为了生成连续 0 的子串而必须消除的 0 的最小数量。

换句话说，问题可以重新表述为：给定一个由0和1组成的字符串，为了使剩下的字符串中包含一段连续的0，需要消除多少个0。

算法

第一步：变量初始化

定义一个计数变量来记录当前零序列的长度。

定义一个 max_count 变量来跟踪迄今为止遇到的最长的零序列。

将两个变量都设置为0。

第二步：字符串遍历

使用循环遍历字符串中的每个字符。

第三步：零检测

如果当前字符为零，则增加计数变量。

第 4 步：一次检测

如果当前字符是 1，则将 count 变量与 max_count 变量进行比较。

如果计数变量高于 max_count 变量，则将 max_count 变量设置为等于计数变量。

将计数变量重置为0。

第 5 步：循环完成

重复这个过程，直到字符串中的所有字符都被处理完。

步骤6：最小删除计算

删除所有零以使剩余的不被任何零分隔所需的最小删除次数可以通过从字符串长度中减去 max_count 来计算。

第7步：结果输出

将结果打印到控制台。

遵循的方法

动态方法

迭代方法

方法一：动态方法

动态规划可以用来高效地解决这个问题。为了创建连续0的子字符串，我们可以创建一个数组dp[]，其中dp[i]表示从子字符串s[0…i]中需要消除的最小数量的0。从空子字符串中消除的最小数量的0是0，因此我们可以将dp[0]初始化为0。

然后，我们可以迭代字符串s并将dp[i]更新为−

如果 s[i] 为“0”，则 dp[i] = dp[i-1]，因为我们可以将 s[i] 包含在连续 0 的子串中或将其删除。

当 s[i] 为“1”时，我们必须获得距离 i 最接近的索引 j，其中包含连续 0 的子串。这可以通过从 i-1 迭代到 0 并查看子字符串 s[j…i] 是否包含连续的 0 来完成。如果找到索引 j，则 dp[i] = dp[j-1] + (i-j+1)，其中 dp[j-1] 表示必须从子串 s[ 中消除的 0 的最小数量0…j-1]和(i-j+1)是为了获得连续0的子串s[j…i]而必须消除的1的总数。如果没有发现这样的索引 j，则 dp[i] = dp[i-1]，因为我们不能将 s[i] 包含在连续 0 的子串中。

最后，为了获得连续 0 的子串，需要从整个字符串 s 中删除的 0 的最小数量由 dp[n-1] 给出，其中 n 是字符串 s 的长度。

示例 1

下面的程序使用我们上面讨论的方法，首先从标准输入读取输入字符串，然后识别所有 0 的子字符串。然后计算最长的 0 子串的长度以及通过连接每个 0 子串生成的字符串的长度。为了确定所需消除的最少次数，它最终从所有 0 子串的总和中减去最长 0 子串的长度，并将结果显示到标准输出。

#include using namespace std;int main() {   string s = "100100011000110"; // constant input string   vector<pair> substrings; // vector to store start and end indices of each substring of 0s   int start = -1;   for (int i = 0; i  maxLength) {         maxLength = len;      }   }   int removals = totalLength - maxLength;   cout << "Input string: " << s << endl;   cout << "Minimum removals: " << removals << endl;   return 0;}

Input string: 100100011000110Minimum removals: 6

#include  #include  using namespace std;  int min_deletions(string str) {    int count = 0, max_count = 0;    for (char c : str) {       if (c == '0') {          count++;       } else {          max_count = max(max_count, count);          count = 0;       }    }     return str.length() - max_count; }  int main() {    string str = "100010011000110";    int deletions = min_deletions(str);    cout << "Minimum deletions needed: " << deletions << endl;    return 0; } 

Minimum deletion needed: 12