使字符串成为由一串0后面跟着一串1组成的最小移除次数-C++-PHP中文网

首页

后端开发

C++

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

王林

Sep 07, 2023 pm 10:57 PM

字符串移除最小次数和

使字符串成为由一串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 <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子字符串的长度之间的差异。

Example 2

的中文翻译为：

示例2

该代码是一个 C++ 软件，它计算从二进制字符串中删除所有零所需的最小消除次数，以便其余的不被任何零分隔。 min_deletions 函数将二进制字符串作为输入，并使用循环来遍历字符串中的每个字符。该循环每次遇到零时都会增加计数变量，并在遇到一时将其重置为零。 count变量的最大值保存在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; 
}