数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究查找大小最多为 3N 的二进制字符串，其中至少包含两个大小为 2N 的给定字符串作为子序列
我们给定三个大小相等且等于 2*N 的字符串，其中 N 是一个整数。我们必须创建一个大小为 3*N 的字符串，并且至少有两个给定的字符串是它的子序列。此外，给定的字符串是二进制字符串，这意味着它们只包含两个不同的字符“0”和“1”。我们将通过遍历字符串并获取 0 和 1 的频率来实现代码。
示例
输入
string str1 = “11”; string str2 = “10”; string str3 = “10”;
输出
110
解释：前两个字符串是给定输出字符串的序列。
输入
string str1 = “001111”; string str2 = “001111”; string str3 = “11000”;
输出
00001111
观察
在给定的问题中，我们有偶数长度的二进制字符串，这意味着只有两个不同的字符。这里我们只有两个字符，因此这两个字符的频率都为 N，或者其中一个字符的频率大于 N，另一个字符的频率小于 N。
例如：如果字符串 1 中“0”的频率大于 N，并且字符串 2 中“1”的频率大于 N。或者，另一种情况是反过来，字符串 2 中“0”的频率大于 N，而字符串 1 中“1”的频率大于 N。现在，第三个字符串的“1”频率将大于或等于 N，这使得它与其中一个字符串具有相同的“1”频率，或者在“0”的情况下，它也与其中一个给定字符串具有相同的“0”频率。
所以，重点是总会有两个字符串存在，其中任何一个字符的频率都大于或等于 N。因此，最终字符串始终可以创建。
方法
在这种方法中，我们将创建一个函数，在其中我们将检查所有三个给定字符串中 1 和 0 的频率。
对于任何两个字符串，如果它们具有相同较高频率的任何字符，我们将选取它们以及频率最高的字符，并将它们传递给另一个函数以计算所需的字符串。
我们将使用双指针技术首先获取所有频率较低的字符，然后获取频率较高的字符。
示例
#include <bits/stdc++.h>
using namespace std;
// function to build the string
string buildString(string str1, string str2, char req){
// using the two pointers approach
int ptr1 = 0, ptr2 = 0;
int len = str1.size();
string ans = "";
while(ptr1 < len && ptr2 < len){
while(ptr1 < len && str1[ptr1] != req){
ans += str1[ptr1];
ptr1++;
}
while(ptr2 < len && str2[ptr2] != req){
ans += str2[ptr2];
ptr2++;
}
// if we are at end break
if(ptr1 == len || ptr2 == len){
break;
}
if(str1[ptr1] == str2[ptr2]){
ans += str1[ptr1];
ptr1++, ptr2++;
} else{
ans += str1[ptr1];
ptr1++;
}
}
// adding the remaining characters
while(ptr1 < len){
ans += str1[ptr1];
ptr1++;
}
while(ptr2 < len){
ans += str2[ptr2];
}
return ans;
}
// function to get the string
string getString(string str1, string str2, string str3){
// getting length of the given strings as given the size of all the strings is same
int len = str1.size();
// creating arrays to store the frequency of the zeroes
int freq[3] = {0};
// getting values for the first string
for(int i=0; i<len; i++){
if(str1[i] == '0'){
freq[0]++;
}
}
// getting values for the second string
for(int i=0; i<len; i++){
if(str2[i] == '0'){
freq[1]++;
}
}
// getting values for the third string
for(int i=0; i<len; i++){
if(str3[i] == '0'){
freq[2]++;
}
}
char req;
// conditions to make the combination of the two string
if((freq[0] >= len/ 2 && freq[1] >= len/2) || (freq[0] <= len/ 2 && freq[1] <= len/2) ){
// frequency of zero or one is more for both first and second string leave the third string away
if(freq[0] >= len/2 && freq[1]>= len/2){
req = '0';
}
else{
req = '1';
}
}
else if((freq[0] >= len/ 2 && freq[2] >= len/2) || (freq[0] <= len/ 2 && freq[2] <= len/2) ){
// frequency of zero or one is more for both first and third string leave the second string away
str2 = str3;
if(freq[0] >= len/2 && freq[2] >= len/2){
req = '0';
} else{
req = '1';
}
} else{
// both initial conditions are false means both second and third string have the frequency of zero or one in same side leave the first string away
str1 = str3;
if(freq[2] >= len/2 && freq[1] >= len/2){
req = '0';
} else{
req = '1';
}
}
// calling function to return the requird string
return buildString(str1, str2, req);
}
int main(){
string str1 = "001111"; // given strings
string str2 = "001111";
string str3 = "001100";
// getting the required string
cout<<"The required string of at most size 3*N is: " << getString(str1, str2, str3 )<<endl;
}
输出
The required string of at most size 3*N is: 00001111
时间和空间复杂度
上述代码的时间复杂度为 O(N)，其中 N 是给定长度的大小，因为我们只遍历字符串一次。
上述代码的空间复杂度为 O(N)，用于存储最终答案。
结论
在这个程序中，我们实现了一个代码来获取大小为 3*N 的字符串，该字符串是三个给定长度为 2*N 的二进制字符串中任意两个字符串的超序列。我们使用了鸽巢原理来证明答案始终存在，然后通过使用双指针并计算频率，我们创建了所需的字符串，时间和空间复杂度为 O(N)。
78 次浏览
