数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究将字符串连接成由 0 组成的子字符串后跟由 1 组成的子字符串所需的最小移除次数
问题“将字符串连接成由 0 组成的子字符串所需的最小移除次数”涉及字符串操作的任务。输入提供一个由 0 和 1 组成的字符串，结果是一个整数，表示为了生成连续的 0 的子字符串而必须删除的 0 的最少数量。
换句话说，问题可以重新表述如下：给定一个由 0 和 1 组成的字符串，必须删除多少个 0 才能使剩余的字符串包含连续的 0 的子字符串。
算法
步骤 1：变量初始化
定义一个计数变量来记录当前 0 序列的长度。
定义一个 max_count 变量来跟踪迄今为止遇到的最长 0 序列。
将这两个变量都设置为 0。
步骤 2：字符串遍历
使用循环遍历字符串中的每个字符。
步骤 3：零检测
如果当前字符为零，则增加计数变量。
步骤 4：一检测
如果当前字符为一，则将计数变量与 max_count 变量进行比较。
如果计数变量大于 max_count 变量，则将 max_count 变量设置为等于计数变量。
将计数变量重置为 0。
步骤 5：循环完成
重复此过程，直到处理完字符串中的所有字符。
步骤 6：最小删除计算
可以通过从字符串的长度中减去 max_count 来计算将所有零移除以使剩余的零不与任何零分隔所需的最小删除次数。
步骤 7：结果输出
将结果打印到控制台。
遵循的方法
动态方法
迭代方法
方法 1：动态方法
动态规划可用于有效地解决此问题。为了创建连续的 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' 时，我们必须获得包含连续 0 的子字符串的最接近 i 的索引 j。这可以通过从 i-1 迭代到 0 并查看子字符串 s[j...i] 是否包含连续的 0 来完成。如果找到索引 j，则 dp[i] = dp[j-1] + (i-j+1)，其中 dp[j-1] 表示必须从子字符串 s[0...j-1] 中删除的 0 的最小数量，而 (i-j+1) 是为了获得连续的 0 的子字符串 s[j...i] 而必须删除的 1 的总数。如果找不到这样的索引 j，则 dp[i] = dp[i-1]，因为我们无法将 s[i] 包含在连续的 0 的子字符串中。
最后，为了从整个字符串 s 中获得连续的 0 的子字符串，需要删除的 0 的最小数量由 dp[n-1] 给出，其中 n 是字符串 s 的长度。
示例 1
下面的程序使用我们上面讨论过的方法，首先从标准输入读取输入字符串，然后识别所有 0 的子字符串。然后计算最长 0 子字符串的长度以及通过连接每个 0 子字符串生成的字符串的长度。为了确定所需的最小消除次数，它最终从所有 0 子字符串的总和中减去最长 0 子字符串的长度，并将结果显示到标准输出。
#include <bits/stdc++.h>
using namespace std;
int main() {
string s = "100100011000110"; // constant input string
vector<pair<int, int>> substrings; // vector to store start and end indices of each substring of 0s
int start = -1;
for (int i = 0; i < s.length(); i++) {
if (s[i] == '0') {
if (start == -1) {
start = i;
}
} else {
if (start != -1) {
substrings.push_back(make_pair(start, i - 1));
start = -1;
}
}
}
if (start != -1) {
substrings.push_back(make_pair(start, s.length() - 1));
}
int totalLength = 0;
for (auto& p : substrings) {
totalLength += p.second - p.first + 1;
}
int maxLength = 0;
for (auto& p : substrings) {
int len = p.second - p.first + 1;
if (len > maxLength) {
maxLength = len;
}
}
int removals = totalLength - maxLength;
cout << "Input string: " << s << endl;
cout << "Minimum removals: " << removals << endl;
return 0;
}
输出
Input string: 100100011000110 Minimum removals: 6
方法 2：迭代方法
此方法使用一种简单的迭代方法来逐个字符地遍历给定的字符串，同时更新两个变量 count 和 max_count 的值。该方法根据当前字符是 0 还是 1 来更新 count 和 max_count 变量。然后它提供 max_count 和最长 0 子字符串的长度之间的差值。
示例 2
代码是一个 C++ 程序，它计算将所有零从二进制字符串中删除所需的最小消除次数，以使剩余的零不与任何零分隔。min_deletions 函数将二进制字符串作为输入，并使用循环遍历字符串中的每个字符。每次遇到零时，循环都会增加一个计数变量，并在遇到一时将其重置为零。计数变量的最大值保存在 max_count 中，最后从字符串的长度中减去 max_count 以获得所需的最小删除次数。然后将结果显示给用户。
#include <iostream>
#include <string>
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
结论
确定所有 0 的子字符串、计算连接每个 0 子字符串的结果字符串的长度以及确定最长 0 子字符串的长度是解决给定问题的三个步骤。然后可以从所有 0 子字符串的总和中减去最长 0 子字符串的长度，以获得所需的最小删除次数。
我们用来获得答案的方法简单有效，并且在线性时间内运行，使其适用于大型输入。但可以通过应用更复杂的方法（例如动态规划）来进一步改进它。
68 次查看
