数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究通过重复将两个连续的 0 替换为单个 1 使给定的二进制字符串相等
在任何编程语言中，二进制字符串都是字符 0 和 1 的集合。在每个阶段，二进制字符串都遵循这样的方法，即字符串只能包含这两个字符。
字符串中的连续字符是指索引差为 1 的字符。让我们考虑两个索引 i 和 j，如果 |j-i| = 1，则称它们是连续的。
在 C++ 中，两个字符串被称为等价，如果 -
两个字符串中对应的字符相同。
字符串的长度相等，并且对应索引处的字符也一致。
以下是一些说明问题陈述的示例 -
示例
str1 - “10001”
str2 - “101”
解决方案 -
str1 无法转换为 str2，因为在转换 str1 以创建 str2 等价字符串时，我们将得到 str1 为 “1011”，而 str2 为 “101”。
示例 2 - 让我们考虑以下输入 -
str1 - “001”
str2 - “11”
解决方案 -
str1 可以转换为 str2，通过将前两个零替换为单个 1。
可以使用 C++ 中的字符匹配和字符串遍历来解决以下问题。
算法
步骤 1 - 使用两个指针 i 和 j 分别同时遍历字符串 s1 和 s2。
步骤 2 - 如果两个索引处的字符匹配，则递增 i 和 j 指针。
步骤 3 - 如果字符不等价，则检查第 i 个和第 (i+1) 个索引处的字符是否为 '0'，以及第 j 个索引处的字符是否为 '1'。
步骤 4 - 如果存在这种情况，则可以执行转换。i 指针递增两个位置，j 指针递增一个索引位置，因为两个零都被转换为一个。
步骤 5 - 如果字符不等价，并且上述情况也不存在，则无法执行转换。
步骤 6 - 如果指针 i 和 j 都成功到达结束位置，则 s1 到 s2 的转换是可能的。
示例
以下代码片段以两个二进制字符串作为输入，并检查是否可以通过根据指定条件简单地替换字符来使这两个字符串等价。
//including the required libraries
#include <bits/stdc++.h>
using namespace std;
//convert consecutive 0's to 1
bool convertBinary(string s1, string s2){
//fetching the lengths of both the strings
int len1 = s1.length();
int len2 = s2.length();
string temp ="";
//maintaining counters of both the strings
int i = 0, j = 0;
//iterating over both the strings simultaneously
while (i < len1 && j < len2) {
//if both the characters are equivalent in nature
//skip to next character
if (s1[i] == s2[j]) {
temp+=s1[i];
//incrementing both pointers
i++;
j++;
}
// if both characters differ
else {
// checking if '00' of s1 can be converted to '1' of s2
if(s2[j]=='1' && s1[i]=='0'){
//checking if i+1th index exists and is equivalent to 0
if(i+1 < len1 && s1[i+1]=='0'){
//conversion is possible
//skip two 0's of s1 since converted to 1 in s2
temp+='1';
i += 2;
j++;
} else {
return false;
}
}
// If not possible to combine
else {
return false;
}
}
}
cout<<"Entered string2 "<<s2<<"\n";
cout<<"Converted string1 "<<temp<<"\n";
//check if both the strings are returned to end position
if (i == len1 && j == len2)
return true;
return false;
}
// calling the conversion rate
int main(){
string str1 = "100100";
string str2 = "1111";
//capturing result
cout<<"Entered string1 "<<str1<<"\n";
bool res = convertBinary(str1, str2);
if (res)
cout << "First string can be converted to second";
else
cout << "First string can't be converted to second";
return 0;
}
输出
Entered string1 100100 Entered string2 1111 Converted string1 1111 First string can be converted to second
结论
由于该方法有效地逐个字符比较输入字符串，因此时间复杂度为 O(min(字符串长度))。字符串遍历是字符串问题解决的一个重要方面。
234 次查看
