最小化字尾翻轉以使二進位制字串非遞減

---

在這個問題中，我們將計算透過翻轉二進位制字串的字元來將字串轉換為非遞減順序所需的最小操作次數。

如果第 p 個索引處的字元為 0 且與前一個索引處的字元不匹配，我們可以翻轉從第 p 個索引開始的子字串的所有字元，並且我們可以計算最小翻轉次數。

問題陳述 - 我們給定一個二進位制字串 alpha。我們需要計算將二進位制字串轉換為遞增順序所需的最小翻轉次數。一次翻轉，我們可以選擇任何索引 p 並翻轉從第 p 個索引開始的子字串。

示例

輸入

alpha = "11000110"

輸出

3

解釋

• 我們可以在第一步翻轉從第二個索引開始的子字串。因此，結果字串將是 11111001。

• 在第二步中，選擇從第五個索引開始的字串並翻轉它。因此，字串變為 11111110。

• 翻轉最後一個字元以使字串等於 1111111。

因此，我們需要執行總共 3 次翻轉才能將字串轉換為遞增順序。

輸入

alpha = "0011"

輸出

0

解釋 - 字串已經是遞增順序。

輸入

alpha = "1100";

輸出

1

解釋 - 我們可以翻轉從第二個索引開始的子字串以獲得 1111 字串。

方法一

在這種方法中，我們將遍歷字串，當我們發現當前字元為 '0' 且與前一個字元不匹配時，我們將翻轉從當前索引右側的所有字元。

演算法

步驟 1 - 將 'cnt' 初始化為 0 以儲存所需的最小翻轉次數。

步驟 2 - 如果索引 p 和 p - 1 處的字元不相同，並且索引 'p' 處的字元為 '0'，請執行以下步驟。

步驟 3 - 從第 p 個索引開始遍歷字串。

步驟 4 - 如果第 q 個索引處的字元為 '0'，則將其替換為 '1'。否則，將其替換為 '0'。

步驟 5 - 將 cnt 值加 1。

步驟 6 - 最後，返回 'cnt' 值。

示例

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

int GetOperations(string alpha) {
   // For storing the count of operations
   int cnt = 0;
   for (int p = 1; p < alpha.length(); p++) {
     // For different adjacent characters
     if (alpha[p] != alpha[p - 1]) {
       if (alpha[p] == '0') {
         //   Flipping all bits of a substring starting from index p
         for (int q = p; q < alpha.length(); q++) {
            if (alpha[q] == '0') {
              alpha[q] = '1';
            } else {
              alpha[q] = '0';
            }
         }
         cnt++;
       }
     }
   }
   // return answer
   return cnt;
}
int main() {
   string alpha = "11000110";
   cout << "The minimum operations required to convert the string into the increasing order is " << GetOperations(alpha);
   return 0;
}

輸出

The minimum operations required to convert the string into the increasing order is 3

時間複雜度 - O(N*N) 來遍歷和翻轉字串字元。

空間複雜度 - O(1)，因為我們不使用任何額外空間。

方法二

在這種方法中，我們將使用布林變數來跟蹤字串字元是否被翻轉，而不是實際翻轉它們。

演算法

步驟 1 - 將 'cnt' 和 'isFlipped' 初始化為 '0'。

步驟 2 - 開始遍歷字串。如果索引 p 和 p - 1 處的字元不匹配，請執行以下步驟。

步驟 3 - 如果 isFlipped 等於 0，並且 alpha[p] 也為 '0'，則將 isFlipped 更改為 1，並將 'cnt' 加 1。

步驟 4 - 如果 isFlipped 為 1，則將 'cnt' 加 1。

步驟 5 - 從函式返回 'cnt'。

示例

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

int GetOperations(string alpha) {
   // For storing the count of operations
   int cnt = 0;
   // To keep track of the flip
   bool isFlipped = 0;
   for (int p = 1; p < alpha.length(); p++) {
     // For different adjacent characters
     if (alpha[p] != alpha[p - 1]) {
       // alpha[p] is '0' and its not equal to alpha[p-1]. So, the string is in decreasing order.
       if (isFlipped == 0 && alpha[p] == '0') {
         isFlipped = 1;
         cnt++;
       }
       // When a string is in increasing order, but the string is flipped
       else if (isFlipped == 1) {
         cnt++;
       }
     }
   }
   // return answer
   return cnt;
}
int main() {
   string alpha = "11000";
   cout << "The minimum operations required to convert the string into the increasing order is " << GetOperations(alpha);
   return 0;
}

輸出

The minimum operations required to convert the string into the increasing order is 1

時間複雜度 - O(N) 來遍歷字串。

空間複雜度 - O(1)

在第二種方法中，我們使用布林變數來跟蹤虛擬翻轉的字元。因此，它減少了每次發現字串不是遞增順序時翻轉所有右側字元的成本。