問題陳述
我們給定了二進制字符串 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之前所需的最小移動次數在二進制字符串中的詳細內容，更多請關注www.xfxf.net其它相關文章！
