資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學經過M次迭代後，將所有01或10轉換為11，從而找到二進位制字串
二進位制字串是由僅兩種不同字元組成的字串，即'0'和'1'。我們將得到一個二進位制字串和數字m。我們必須應用操作將所有連續出現的'01'和'10'轉換為'11'。還有一個條件是'0'只有一個鄰居可以是'1'。我們最多隻能遍歷字串m次，其中m是給定的。
讓我們透過以下示例來理解
Input 1: Given binary string: ‘01000101’ Given number: 2 Output: 111011101
解釋
我們將首先遍歷字串，並可以更改恰好只有一個'1'作為鄰居的零，這使得我們的字串變為'111011101'。在第二次迭代中，字串將保持不變，因為沒有零恰好只有一個'1'作為鄰居。
Input 2: Given binary string: ‘00100’ Given number: 1000 Output: 11111
解釋
第一次迭代後，我們將得到01110，第二次迭代後，我們將得到11111。對於其餘的迭代，字串將不會發生變化。
方法
我們已經看到了上面給定字串的示例，讓我們來看一下方法：
首先，我們將建立一個函式，該函式將給定的字串和數字作為引數，並將所需的字串作為返回值。
在函式中，我們將找到字串長度和給定迭代次數中的最小值，因為字串在給定迭代次數內將發生最大變化。
然後，我們將迭代給定迭代次數的字串，並在每次迭代中找到零。
如果零位於兩個一或零之間，我們將移動，否則我們將零更新為一，然後移動到該位置。
從主函式中，我們將呼叫該函式，並在呼叫該函式後列印最終答案。
示例
#include <iostream>
using namespace std;
string updateString(string str, int m){
// using the optimal concept to reduce the number of iterations
int n = str.size(); // getting the size of the string
m = min(m,n); // getting the minimum value
// iterating using a while loop
while(m--){
// iterating over the string
for(int i=0; i<n; i++){
if(str[i] == '0'){
if(i == 0){
if(str[i+1] == '1'){
str[i] = '1';
}
}
else if(i == n-1){
if(str[i-1] == '1'){
str[i] = '1';
}
}
else{
if((str[i-1] == '1' || str[i+1] == '1') && (str[i-1] != str[i+1])){
str[i] = '1';
}
}
}
}
}
// returning the string
return str;
}
// main function
int main(){
string str = "01000101";// given string
int m = 2; // given number
// calling the function to update the string
string update_str = updateString(str, m);
cout<<"The given string "<< str << " after " << m << " number of iterations is "<< update_str<<endl;
return 0;
}
輸出
The given string 01000101 after 2 number of iterations is 11110101
時間和空間複雜度
上述程式碼的時間複雜度為O(min(M, N)*N)，其中N是字串的大小，M是我們對字串執行的總迭代次數。
上述程式碼的空間複雜度為O(N)，因為我們將字串作為引數傳遞給給定函式。
使用標誌方法
在之前的方法中，我們迭代了M或字串長度的最小值次數的字串。我們可以透過使用標誌來標記字串沒有改變來降低時間複雜度。
示例
#include <iostream>
using namespace std;
string updateString(string str, int m){
// using the optimal concept to reduce the number of iterations
int n = str.size(); // getting the size of the string
m = min(m,n); // getting the minimum value
bool flag = true;
// iterating using while loop
while(m-- && flag){
flag = false; // marking the flag as false
// iterating over the string
for(int i=0; i<n; i++){
if(str[i] == '0'){
if(i == 0){
if(str[i+1] == '1'){
str[i] = '1';
flag = true;
}
}
else if(i == n-1){
if(str[i-1] == '1'){
str[i] = '1';
flag = true;
}
}
else{
if((str[i-1] == '1' || str[i+1] == '1') && (str[i-1] != str[i+1])){
str[i] = '1';
flag = true;
}
}
}
}
}
// returning the string
return str;
}
// main function
int main(){
string str = "00100";// given string
int m = 1000; // given number
// calling the function to update the string
string update_str = updateString(str, m);
cout<<"The given string "<< str << " after " << m << " number of iterations is "<< update_str<<endl;
return 0;
}
輸出
The given string 00100 after 1000 number of iterations is 11111
結論
在本教程中，我們實現了一個程式，用於在M次迭代後透過將所有01或10轉換為11來查詢二進位制字串。我們實現了一種時間複雜度為O(min(M, N)*N)和空間複雜度為O(N)的方法，其中N是字串的大小，M是給定的整數（我們必須執行的總迭代次數）。此外，我們使用了標誌來減少如果字串沒有改變的迭代次數。
瀏覽量：160
