資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學最小化移除0子串以從迴圈二進位制字串中移除所有0
在這個問題中，我們需要從給定的二進位制字串中移除所有零。此外，我們需要一次移除一對連續的零，並計算移除的零對的總數。
我們可以透過計算給定字串中連續零對的數量來解決這個問題。在本教程中，我們將學習兩種不同的解決方案來解決這個問題。
問題陳述 − 我們給定長度為N的迴圈二進位制字串str。我們需要找到移除字串中所有零所需的最小連續零數。
示例
Input – str = "0011001"
Output – 2
解釋
我們可以一起移除str[0]和str[1]。之後，我們可以移除str[4]和str[5]。所以，我們需要移除2對連續的零。
Input – str = ‘0000000’
Output – 1
解釋
我們可以一次移除所有零。
Input – str = ‘00110010’
Output – 2
解釋
由於二進位制字串是迴圈的，我們可以一起移除str[0]、str[1]和str[7]。接下來，我們可以一起移除str[5]和str[6]。
方法1
在這種方法中，我們將找到給定字串中連續零對的總數，這將回答給定的問題。
演算法
步驟1 − 將‘cnt’變數初始化為零。
步驟2 − 將‘isOne’變數初始化為false值，以跟蹤給定字串中的1。
步驟3 − 使用迴圈遍歷字串。在迴圈中，如果當前字元為‘0’，則將‘cnt’的值增加1。
步驟4 − 使用while迴圈進行迭代，直到我們繼續找到‘0’作為下一個字元，並將‘I’的值增加1。
步驟5 − 如果當前字元為‘1’，則將‘isOne’變數的值更改為true，表示字串至少包含一個‘1’。
步驟6 − 迴圈迭代完成後，如果‘isOne’的值為false，則表示字串僅包含零。在這種情況下，返回1。
步驟7 − 如果第一個和最後一個字元為‘0’，則將‘cnt’的值減少1，因為字串是迴圈的。
步驟8 − 返回‘cnt’的值。
示例
#include <bits/stdc++.h>
using namespace std;
int countRemovels(string str, int N){
// to store the count of 0s
int cnt = 0;
bool isOne = false;
// Iterate over the string
for (int i = 0; i < N; i++){
// If the current character is 0, increment the count of 0s
if (str[i] == '0'){
cnt++;
// traverse the string until a 1 is found
while (str[i] == '0'){
i++;
}
}
else{
// If the current character is 1, then set isOne as true
isOne = true;
}
}
// If string contains only 0s, then return 1.
if (!isOne)
return 1;
// If the first and last character is 0, then decrement the count, as the string is circular.
if (str[0] == '0' && str[N - 1] == '0'){
cnt--;
}
// return cnt
return cnt;
}
int main(){
string str = "0011001";
int N = str.size();
cout << "The total number of minimum substrings of consecutive zeros required to remove is - " << countRemovels(str, N);
return 0;
}
輸出
The total number of minimum substrings of consecutive zeros required to remove is - 2.
空間複雜度 − O(1)
方法2
在這種方法中，我們將透過計算不同的相鄰元素來計算移除所有零所需的最小零子串移除次數。
演算法
步驟1 − 定義‘cnt’和‘isOne’變數，並分別初始化為0和false。
步驟2 − 使用for迴圈進行N-1次迭代，其中N是字串的長度。
步驟3 − 在迴圈中，檢查當前字元是否為‘0’，下一個字元是否為‘1’，將‘cnt’的值增加1。否則，將‘isOne’變數的值更改為true。
步驟4 − 如果最後一個字元為‘0’且第一個字元為‘1’，則將‘cnt’的值增加1。
步驟5 − 如果‘isOne’的值為false，則返回1。
步驟6 − 返回‘cnt’變數的值。
示例
#include <bits/stdc++.h>
using namespace std;
int countRemovels(string str, int N){
// to store the count of 0s
int cnt = 0;
// to check if there is at least one 1
bool isOne = false;
// traverse the string
for (int i = 0; i < N - 1; i++) {
// if the current character is 0, the next is 1, then increment count by 1
if (str[i] == '0' && str[i + 1] == '1'){
cnt++;
}
else{
// if the current character is 1, then set isOne to true
isOne = true;
}
}
// for circular string, if the last character is 0 and the first is 1, then increment count by 1
if (str[N - 1] == '0' && str[0] == '1'){
cnt++;
}
// if there is no 1 in the string, then return 1
if (!isOne){
return 1;
}
return cnt; // return cnt
}
int main(){
string str = "0011001";
int N = str.size();
cout << "The total number of minimum substrings of consecutive zeros required to remove is - " << countRemovels(str, N);
return 0;
}
輸出
The total number of minimum substrings of consecutive zeros required to remove is - 2
結論
我們已經看到了給定問題的兩種不同的解決方案。在第一種方法中，我們計算連續零對的總數；在第二種方法中，我們計算不相鄰相鄰字元的總數。
83 次瀏覽
