我們給定了二進位字串 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 儲存在左側，另一個陣列將所有 0 儲存在右側。之後，我們可以將兩個陣列中第 i 個索引處的元素相加，並找到最小總和。
第 1 步 - 定義長度為 n 的「零」和「一」命名列表，其中 n 是我們可以使用 size() 方法取得的字串的長度。 < /p>
步驟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 的計數。
此方法是第一種方法的最佳化版本。在這裡，我們使用兩個變數來儲存 1 和 0 的計數，而不是列表。
第 1 步 - 定義「zeros_right」變數並使用 0 進行初始化。
第 2 步 - 遍歷字串，計算給定字串中「0」字元的總數，並據此更新「zero_right」變數的值。 < /p>
第 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中文網其他相關文章！
