將子串“01”替換為“110”以完全移除它所需的最小替換次數

---

將子串“01”替換為“110”以完全移除它所需的最小替換次數是字串操作和最佳化中的一個常見問題。在本教程中，我們將深入探討這個問題，並使用C++提出一個有效的解決方案。

這個問題需要找到所需的最小替換次數，透過將二進位制字串中所有出現的子串“01”替換為“110”，同時確保生成的字串不包含子串“10”。

我們詳細解釋了問題陳述，提出了一種演算法方法來解決它，並提供了C++的逐步實現。在本教程結束時，讀者將清楚地瞭解這個問題，並將掌握解決涉及字串轉換的類似場景的實用解決方案。

問題陳述

給定一個二進位制字串S。目標是確定將S中所有出現的子串“01”轉換為字串“110”所需的最小替換次數，使得S中不再存在子串“01”。

讓我們用例子來理解這個陳述。

示例1

輸入

S = “01”

輸出

Minimum number of replacements required: 1

解釋

字串“01”中的子串(0, 1)被選中並替換為“110”，結果修改後的字串為“110”。

執行上述操作後，字串S（現在等於“110”）不再包含子串“01”。因此，只需要一次操作即可實現。

示例2

輸入

S = “001”

輸出

Minimum number of replacements required: 3

解釋

步驟1：字串“001”中的子串(1, 2)被選中並替換為“110”，結果修改後的字串為“0110”。

步驟2：接下來，字串“0110”中的子串(0, 1)被選中並替換為“110”，結果修改後的字串為“11010”。

步驟3：最後，字串“11010”中的子串(2, 3)被選中並替換為“110”，結果修改後的字串為“111100”。

執行上述操作後，字串S（現在等於“111100”）不再包含任何子串“01”。因此，所需的總操作次數為3。

演算法

步驟1. 定義一個函式‘minimumOperations’，它以二進位制字串‘S’及其長度‘N’作為輸入。

步驟2. 將‘ans’初始化為0以儲存執行的運算元，並將‘cntOne’初始化為0以儲存遇到的1的數量。

步驟3. 使用一個迴圈從末尾遍歷字串‘S’，其中‘i’初始化為‘N - 1’。

步驟4. 在迴圈內，檢查當前字元‘S[i]’是否為'0'。

• 如果是'0'，則將遇到的1的數量‘cntOne’新增到答案‘ans’中。

• 將遇到的1的數量‘cntOne’加倍（乘以2）。

步驟5. 如果當前字元‘S[i]’是'1'，則將遇到的1的數量‘cntOne’加1。

步驟6. 迴圈結束後，列印所需的最小替換次數：“所需的最小替換次數：”後面跟著‘ans’的值。

步驟7. 在‘main’函式中，宣告一個二進位制字串‘S’及其長度‘N’，然後呼叫‘minimumOperations’函式，並將‘S’和‘N’作為引數傳遞。

此演算法有效地計算根據給定條件轉換二進位制字串所需的最小替換次數。

示例

使用C++實現上述演算法

下面的C++程式解決了查詢所需最小替換次數的問題，該問題透過將子串“01”替換為“110”來轉換二進位制字串，同時確保轉換後的字串不包含子串“10”。該程式使用一種演算法，該演算法從末尾迭代字串並跟蹤遇到的1的數量。它透過考慮0的出現並相應地更新1的數量來計算替換次數。最後，它列印所需的最小替換次數。

#include <iostream>
#include <string>
// The function aims to determine the minimum count of replacements required to change every occurrence of "01" to "110"
// In order to avoid having the substring "10" within string S
void minimumOperations(std::string S, int N) {
   int ans = 0; // Keeps track of the total number of operations executed
   int cntOne = 0; // Holds the resulting count of substrings
   // Iterate through the string S starting from the last character
   for (int i = N - 1; i >= 0; i--) {
      if (S[i] == '0') { // In the case where the current character is 0
         ans += cntOne; // Add the count of ones encountered so far to the answer
         cntOne *= 2; // Double the count of ones encountered so far
      } else {
         cntOne++; // If the current character is 1, increment the count of ones encountered so far
      }
   }
   std::cout << "Minimum number of replacements required: " << ans;
}
int main() {
   std::string S = "01";
   int N = S.length();
   minimumOperations(S, N);
   return 0;
}

輸出

Minimum number of replacements required: 1

結論

總而言之，本教程有效地解決了查詢所需最小替換次數的問題，該問題透過將子串“01”替換為“110”來消除所有出現的子串“01”，同時避免子串“10”。我們提供了對問題陳述的全面解釋，概述了一種演算法解決方案，並提供了C++的詳細實現。透過理解基本概念並遵循分步方法，讀者可以自信地解決類似的字串操作難題。