資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
