最小化交替子序列的數量以劃分給定的二進位制字串和子序列編號

---

本文旨在實現一個程式，最小化交替子序列的數量以劃分給定的二進位制字串和子序列編號。

在這裡，您將獲得一個作為問題一部分的二進位制字串。為了防止任何子序列包含相鄰的零和一，我們必須減少子序列的數量並輸出與每個字串元素對應的子序列編號。

子序列表示一個序列，可以透過取給定序列並消除零個或多個成員來建立，同時保持剩餘元素的初始位置。

輸入

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++ 程式設計程式碼以及最小化交替子序列的數量以劃分給定的二進位制字串和子序列編號的演算法。