数据结构
网络
关系数据库管理系统 (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
