將所有0放在1之前所需的最小移動次數在二進位字串中

問題陳述

我們給定了二進位字串 str，我們要求從字串中刪除最少的字符，以便我們可以將所有零放在 1 之前。

範例

輸入

str = ‘00110100111’

輸出

3

說明

這裡，我們可以透過兩種方式實現輸出3。

我們可以從字串中刪除 arr[2]、arr[3] 和 arr[5] 或 arr[4]、arr[6] 和 arr[7]。

輸入

str = ‘001101011’

輸出

2

說明

我們可以刪除 arr[4] 和 arr[6]，將所有零放在 1 之前。

輸入

str = ‘000111’

輸出

0

說明

在給定的字串中，所有零都已放置在 1 之前，因此我們不需要從給定字串中刪除任何字元。

方法 1

在第一種方法中，我們將使用兩個陣列。第一個陣列將所有 1 儲存在左側，另一個陣列將所有 0 儲存在右側。之後，我們可以將兩個陣列中第 i 個索引處的元素相加，並找到最小總和。

演算法

• 第 1 步 - 定義長度為 n 的「零」和「一」命名列表，其中 n 是我們可以使用 size() 方法取得的字串的長度。

• 步驟2 - 如果給定字串中的第一個字元是“1”，則將1 儲存在“ones”陣列的第0 個索引處；否則，存儲0。

• 步驟 3 - 使用 for 迴圈從字串的第二個元素開始遍歷。在 for 迴圈中，使用根據第 i 個索引處的字串的字元將 Ones[i-1] 與 1 或 0 相加得到的結果值來初始化 Ones[i]。

• 第 4 步 - 根據給定字串中的最後一個字符，將 1 或 0 儲存在 Zeros[n-1] 處。

• 步驟 5 - 使用 for 迴圈從最後第二個字元開始遍歷字串，並根據字串字元更新零清單的值。

• 第 6 步 - 定義「min_zeros_to_remove」變數並使用最大整數值對其進行初始化。

• 第 7 步 - 現在，遍歷「零」和「一」清單。從零列表中的“i 1”索引和“一”列表中的“I”索引存取值。之後，加入這兩個元素。

• 步驟 8 - 如果「min_zeros_to_remove」的值小於「min_zeros_to_remove」變數的目前值，則將其值變更為兩個陣列元素的總和。

• 步驟 9 - 傳回結果值。

範例

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

int minimumZeroRemoval(string str){
   int n = str.size();
   // arrays to store the prefix sums of zeros and ones
   vector<int> zeros(n);
   vector<int> ones(n);
   // compute total number of 1s at the left of each index
   ones[0] = (str[0] == '1') ? 1 : 0;
   for (int i = 1; i < n; i++) {
      ones[i] = ones[i - 1] + ((str[i] == '1') ? 1 : 0);
   }
   // compute total number of 0s at the right of each index
   zeros[n - 1] = (str[n - 1] == '0') ? 1 : 0;
   for (int i = n - 2; i >= 0; i--){
      zeros[i] = zeros[i + 1] + ((str[i] == '0') ? 1 : 0);
   }
   // do the sum of zeros and ones for each index and return the minimum value
   int min_zeros_to_remove = INT_MAX;
   for (int i = 0; i < n - 1; i++){
      min_zeros_to_remove = min(min_zeros_to_remove, zeros[i + 1] + ones[i]);
   }
   return min_zeros_to_remove;
}
int main() {
   string str = "00110100111";
   int count = minimumZeroRemoval(str);
   cout << "The minimum number of zeros required to remove from the given string is - " << count;
   return 0;
}

輸出

The minimum number of zeros required to remove from the given string is - 3

• 時間複雜度 - O(N)，因為我們需要 for 迴圈來遍歷大小為 N 的字串和清單。

• 空間複雜度 - O(N)，因為我們使用兩個清單來儲存 1 和 0 的計數。

方法2

此方法是第一種方法的最佳化版本。在這裡，我們使用兩個變數來儲存 1 和 0 的計數，而不是列表。

演算法

• 第 1 步 - 定義「zeros_right」變數並使用 0 進行初始化。

• 第 2 步 - 遍歷字串，計算給定字串中「0」字元的總數，並據此更新「zero_right」變數的值。

• 第 3 步驟 - 定義「ones_left」變數並初始化為 0。

• 步驟 4 - 使用 for 迴圈遍歷字串。如果字串中第 i 個索引處的字元為“1”，則將“ones_left”變數的值增加 1。否則，將「zeros_right」變數的值減少 1。

• 第 5 步 - 如果「zeros_right Ones_left」小於「res」變數的目前值，則更新「res」變數的值。

範例

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

// function to remove zeros from the string to place all zeros before 1.
int minimumZeroRemoval(string str){
   // counting the total number of zeros in the given string
   int zeros_right = 0;
   for (int i = 0; i < str.size(); i++) {
      if (str[i] == '0')
      zeros_right += 1;
   }
   // variable to store the number of ones from left
   int ones_left = 0;
   // Size of the string
   int len = str.size();
   // variable to store the final result
   int result = INT_MAX;
   // Traverse the string from left to right
   for (int i = 0; i < len; i++){
      // If the current character is '1', then increment ones_left by 1 else, decrement zeros_right by 1
      if (str[i] == '1') {
         ones_left += 1;
      } else {
         zeros_right -= 1;
      }
      // Store the minimum result and zeros_right + ones_left in result
      result = min(result, zeros_right + ones_left);
   }
   // Return the final result
   return result;
}
int main() {
   string str = "001101011";
   int count = minimumZeroRemoval(str);
   cout << "The minimum number of zeros required to remove from the given string is - " << count;
   return 0;
}

輸出

The minimum number of zeros required to remove from the given string is - 2

• 時間複雜度 - O(N)，當我們迭代字串時。

• 空間複雜度 - O(1)，因為我們只使用常數空間。

結論

使用者學習了兩種從給定二進位字串中刪除最少字元的方法。第二種方法的程式碼更具可讀性，因為我們使用變數來儲存零和一的計數，而不是使用列表。

以上是將所有0放在1之前所需的最小移動次數在二進位字串中的詳細內容。更多資訊請關注PHP中文網其他相關文章！