資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究二進位制字串中將所有 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
解釋
在給定的 str 中，所有零都已放在 1 之前，因此我們不需要從給定的字串中移除任何字元。
方法 1
在第一種方法中，我們將使用兩個陣列。第一個陣列在左側儲存所有 1，另一個數組在右側儲存所有 0。之後，我們可以在兩個陣列的第 i 個索引處新增元素並找到最小和。
演算法
步驟 1 - 定義名為 ‘zeros’ 和 ‘ones’ 的長度為 n 的列表，其中 n 是字串的長度，我們可以使用 size() 方法獲取。
步驟 2 - 如果給定字串中的第一個字元是 ‘1’，則在 ‘ones’ 陣列的第 0 個索引處儲存 1；否則，儲存 0。
步驟 3 - 使用 for 迴圈遍歷字串的第二個元素。在 for 迴圈中，使用我們根據字串在第 i 個索引處的字元獲得的結果值初始化 ones[i]。
步驟 4 - 根據給定字串中的最後一個字元，在 zeros[n-1] 中儲存 1 或 0。
步驟 5 - 使用 for 迴圈從最後一個第二個字元遍歷字串，並根據字串字元更新 zeros 列表的值。
步驟 6 - 定義 ‘min_zeros_to_remove’ 變數並將其初始化為最大整數值。
步驟 7 - 現在，遍歷 ‘zeros’ 和 ‘ones’ 列表。從 zeros 列表中訪問 ‘i+1’ 索引處的值，從 ‘ones’ 列表中訪問 ‘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)，因為我們只使用常量空間。
結論
使用者學習了兩種從給定二進位制字串中移除最少字元的方法。第二種方法的程式碼更易讀，因為我們使用變數來儲存零和一的計數，而不是使用列表。
183 次檢視
