生成连续的 0 和 1 子字符串所需的最小翻转次数


连续字符序列,称为 0 和 1 的子字符串,可以通过以任何顺序从原始字符串中选择零个或多个字符来创建,而无需跳过任何字符。

例如,字符串“0101”。遵循此文本的子字符串为:0,“”、1、“01”、“10”、“010”、“101”和“0101”。

空字符串也是所有字符串的子字符串,因为它可以通过从原始字符串中精确选择 0 个字符来创建。

因此,在本例中,“”也是“0101”的子字符串。

方法

  • 使用动态规划

  • 使用贪心算法

方法 1:使用动态规划

动态规划是一种有效的方法,可以确定生成连续的 0 和 1 子字符串所需的最小翻转次数。动态规划方法将问题分解成更小的子问题,并自下而上构建解决方案。

我们必须确定获得此类子字符串所需的最小翻转次数。

语法

min (k5):
   l8 [0][0] = 0 
   if k5 [0] == '0'
   else 1
   l8 [0][1] = 0 
   if k5 [0] == '1'
   else 1

      l8[i][0] = l8[i-1][1] + (0 if k5[i] == '0' else 1)
      l8[i][1] = l8[i-1][0] + (0 if k5[i] == '1' else 1)

   // Returning the minimum required
   return minimum among(l8[n-1][0], l8[n-1][1])

算法

计算每个配对字符串中生成连续的 0 和 1 子字符串所需的翻转次数的算法 -

步骤 1  −   初始化两个变量,flip_zero 和 flip_one 为 0。

步骤 2  − 通常建议仔细阅读字符串中的每个字符以确保重复。

  • 如果当前字符与前一个字符不匹配,请查看它是 '0' 还是 '1'。

  • 如果当前字符是 '0',则将 flip_zero 加 1。

  • 如果当前字符是 '1',则将 flip_one 加 1。

步骤 3  −  返回 flip_zero 和 flip_one 的最小值。

此算法计算更改字符串的 0 和 1 所需的翻转次数。根据当前字符的值,每次遇到新字符时,flip_zero 或 flip_one 都会增加。翻转零和一的最小值是最终结果。

示例 1

在此实现中,minFlips 函数迭代字符串 s,计算相邻字符不同的次数。此计数反映了生成连续的 0 和 1 子字符串所需的翻转频率。此计数的最小值和包含与相邻字符相同的字符的连续 0 或 1 子字符串的数量表示无需翻转的次数。

我们在示例主方法中使用字符串“0011100”调用 minFlips 并打印结果,结果为 1。根据此结果,可以通过仅翻转一次来生成输入字符串中的连续的 0 和 1 子字符串。

#include <iostream>
#include <string>
#include <algorithm>

int minFlips (std::string s) {
   int n = s.size();
   int count = 0;
   for (int i = 0; i < n - 1; i++) {
      if (s[i]!= s[i+1]) {
         count++;
      }
   }
   return std::min(count, n - count - 1);
}
int main () {
   std::string s = "0011100";
   std::cout << "Minimum flips required: " << minFlips(s) << std::endl;
   return 0;
}

输出

Minimum flips required: 2

使用贪心算法

为了获得整体最优解,贪心算法需要在每个阶段做出局部最优决策。确定生成连续的 0 和 1 子字符串所需的最小翻转次数是此技术的应用之一。

通常,问题陈述指的是具有交替的 0 和 1 子字符串的二进制字符串。目标是确定将字符串更改为所有 0 或所有 1 出现在另一侧之前的模式所需的最小翻转次数。

算法

为了找到每个字符串中生成连续的 0 和 1 子字符串所需的最小翻转次数,我们可以遵循以下算法 -

  • 步骤 1 − 我们需要设置两个变量,它们将保存初始值为 0。第一个变量 c1 表示为了生成序列 010101 而所需的翻转次数。另一方面,第二个变量 c2 表示我们需要执行多少次翻转才能创建序列 101010。

  • 步骤 2 − 遍历字符串,对于每个字符,检查它是否根据当前模式匹配预期字符。如果不是,则增加相应的 c 变量。

  • 步骤 3 − 检查当前字符后,根据当前模式翻转预期字符。例如,如果当前模式是 010101... 并且当前字符是 1,则下一个预期字符将是 0。

  • 步骤 4 − 如果生成相反模式所需的翻转次数小于当前模式,则切换模式。

  • 步骤 5 − 返回 c1 和 c2 的最小值。

  • 步骤 6 − 此算法采用 n(输入字符串的长度)作为输入,并且具有 O(n) 的时间复杂度。

示例 2

在此示例中,minFlips 函数以二进制字符串 s 作为输入,并输出生成交替的 0 和 1 字符串所需的最小翻转次数。该函数通过计算生成每个字符串所需的翻转次数来生成两个可能的交替字符串,一个以 0 开头,另一个以 1 开头。然后,该函数返回这两个数字中较小的一个。

在主函数中,我们使用二进制字符串“0101010101”调用 minFlips 并将结果打印到控制台。输出应为“所需的最小翻转次数:0”,因为输入字符串已经是交替的 0 和 1 字符串。由于输入字符串已经是交替的 0 和 1 字符串,因此结果应该说“所需的最小翻转次数:0”。

#include <iostream>
#include <string>

using namespace std;

int minFlips(string s) {
   int n = s.length();
   int flips1 = 0, flips2 = 0;

   // Count flips required to generate string of alternating 0's and 1's
   for (int i = 0; i < n; i++) {
      if (i % 2 == 0 && s[i] != '0') {
         flips1++;
      } else if (i % 2 == 1 && s[i] != '1') {
         flips1++;
      }
      if (i % 2 == 0 && s[i] != '1') {
         flips2++;
      } else if (i % 2 == 1 && s[i] != '0') {
         flips2++;
      }
   }

   // Return the minimum number of flips required
   return min(flips1, flips2);
}
int main() {
   string s = "0101010101";
   int flips = minFlips(s);
   cout << "Minimum flips required: " << flips << endl;
   return 0;
}

输出

Minimum flips required: 0

结论

确定生成连续的 0 和 1 子字符串所需的最小翻转次数的挑战的解决方案取决于问题的限制和要求。执行此操作所需的最小翻转次数取决于字符串以及如何定义“连续”子字符串。在解决问题时,通常可以采用多种方法。例如,动态规划和贪婪算法都是解决类似问题的可能解决方案。

具体来说,如果您需要找到问题的最佳解决方案,则动态规划可能是您的最佳选择。使用此技术,您可以创建一个数据库,其中包含有关生成可行子字符串直至特定点所需的翻转次数的信息。虽然此方法确实有其优点,但如果我们想找到此问题的最佳解决方案,则各种解决方案的缺点至关重要。

更新时间: 2023 年 7 月 31 日

943 次查看

开启您的 职业生涯

通过完成课程获得认证

开始学习
广告