最小化交替子序列的数量以划分给定的二进制字符串和子序列编号

---

本文旨在实现一个程序，最小化交替子序列的数量以划分给定的二进制字符串和子序列编号。

在这里，您将获得一个作为问题一部分的二进制字符串。为了防止任何子序列包含相邻的零和一，我们必须减少子序列的数量并输出与每个字符串元素对应的子序列编号。

子序列表示一个序列，可以通过取给定序列并消除零个或多个成员来创建，同时保持剩余元素的初始位置。

输入

Let us consider the Input: str = “10010100”, and the length given is equal to 8.

输出

3
1 1 2 2 2 2 2 3

说明 − 可能存在至少三个子序列，没有任何相邻的 1 或 0。

输入

Let us consider the Input: str = “10000”, and the length given is equal to 5.

输出

4
1 1 2 3 4 

说明 − 可能存在至少四个子序列，没有任何相邻的 1 或 0。

输入

Let us consider the Input: str = “101101”, and the length given is equal to 6.

输出

2
1 1 1 2 2 2

说明 − 可能存在至少两个子序列，没有任何相邻的 1 或 0。

输入

Let us consider the Input: str = “10001000”, and the length given is equal to 8.

输出

5
1 1 2 3 3 3 4 5

说明 − 可能存在至少五个子序列，没有任何相邻的 1 或 0。

问题陈述

实现一个程序来最小化交替子序列的数量以划分给定的二进制字符串和子序列编号。

算法

下面给出了最小化交替子序列的数量以划分给定的二进制字符串和子序列编号的算法：

• 步骤 1 − 定义一个函数 findSubsequences(string str, int length)。

  此函数确定 str 必须划分成的子序列的最小数量，以及 str 中每个字符所属的子序列。

• 步骤 2 − 现在定义一个向量。

  此向量中存储着 str 中每个字符所属的子序列。

• 步骤 3 − 为了遍历字符串 str 的每个字符，添加一个循环。

• 步骤 4 − 定义一个变量 newSubsequence，它跟踪将创建多少个附加子序列。

• 步骤 5 − 检查字符是否为'0'。

• 步骤 6 − 如果不存在以 '1' 结尾的字符串，则将 newSubsequence 添加到 zeroSubSeq。否则，将 oneSubSeq 的最后一个元素放入 newSubsequence 并删除 oneSubSeq 的最后一个元素。

• 步骤 7 − 如果不存在以 '0' 结尾的字符串，则将 newSubsequence 添加到 oneSubSeq。否则，将 zeroSubSeq 的最后一个元素放入 newSubsequence 并删除 zeroSubSeq 的最后一个元素。

• 步骤 8 − 打印获得的子序列的最小数量。

示例（C++程序）

这是上面编写的算法的 C++ 程序实现，用于最小化交替子序列的数量以划分给定的二进制字符串和子序列编号

#include <bits/stdc++.h>
using namespace std;

void findSubsequences(string str, int length){
   vector<int> result(length);
   vector<int> zeroSubSeq,oneSubSeq ;
   for (int i = 0; i < length; ++i) {
      int newSubsequence = zeroSubSeq.size() + oneSubSeq.size();
      if (str[i] == '0') {
         if (oneSubSeq.empty()) {
            zeroSubSeq.push_back(newSubsequence);
         } else {
            newSubsequence = oneSubSeq.back();
            oneSubSeq.pop_back();
            zeroSubSeq.push_back(newSubsequence);
         }
      } else {
         if (zeroSubSeq.empty()) {
            oneSubSeq.push_back(newSubsequence);
         } else {
            newSubsequence = zeroSubSeq.back();
            zeroSubSeq.pop_back();
            oneSubSeq.push_back(newSubsequence);
         }
      }
      result[i] = newSubsequence;
   }
   cout << zeroSubSeq.size() + oneSubSeq.size() << endl;
   for (int i = 0; i < length; ++i) {
      cout << result[i] + 1 << " ";
   }
}
int main(){
    string str = "10010100";
    int length = 8;
    findSubsequences(str, length);
    return 0;
}

输出

执行后，它将产生以下输出：

3
1 1 2 2 2 2 2 3

结论

同样，我们可以找到一种方法来最小化交替子序列的数量以划分给定的二进制字符串和子序列编号。本文解决了获得程序以最小化交替子序列的数量以划分给定的二进制字符串和子序列编号的挑战。

这里提供了 C++ 编程代码以及最小化交替子序列的数量以划分给定的二进制字符串和子序列编号的算法。