C++ 在K个步骤中通过对子字符串执行异或操作来最大化二进制字符串的值
在这个问题中,我们将通过对给定二进制字符串的子字符串执行K个异或操作来最大化二进制字符串的值。
为了最大化任何二进制字符串,我们应该最大化从最左边的零开始的子字符串。例如,为了最大化’11001’字符串,我们需要选择另一个子字符串,以便最大化’001’子字符串。
问题描述 - 我们给出了一个名为bin_str的二进制字符串,其中包含N个字符。我们需要通过对任意两个子字符串进行异或操作来在K个操作中最大化二进制字符串的值。已知子字符串可以是相同的、相交的或非相交的。
示例示例
输入
bin_str = "1101"; K = 1;
输出
1111
解释
我们可以取10和1101子字符串,当我们对两者执行XOR运算时,我们得到1111最大字符串。
输入
bin_str = "110101"; K = 2
输出
111110
解释
- 在第一次操作中,我们取出了110101和1010两个子串。当我们对这两个子串进行XOR操作时,得到了111111的二进制字符串。
-
在第二次操作中,我们取出了111111和1这两个子串。当我们对这两个子串进行XOR操作时,得到了111110,这是我们能够得到的最大字符串。
输入
bin_str = "01"; K = 1;
输出
1
解释:
获取01和0子字符串以生成1。
方法1
在这个方法中,我们将从最左边的0到结尾取一个子字符串,并找到字符串的另一个子字符串以获取最大的二进制字符串值。
例如,二进制字符串是1110010101。为了最大化二进制字符串,我们需要最大化0010101子字符串。因此,我们将二进制字符串本身作为一个子字符串,另一个长度相同的字符串‘0010101’一起使用,以最大化二进制字符串。
算法:
- 第一步 - 执行maxValUtil()函数K次,并使用其返回值更新二进制字符串。
-
第二步 - 在maxValUtil()函数中,将”leftZero”初始化为-1,用于存储最左侧零的索引,将”cnt0″和”cnt1″初始化为0,用于分别存储二进制字符串中0和1的计数。
-
第三步 - 遍历字符串,如果当前字符为”1″,则将”cnt1″加1。否则,如果”leftZero”为-1,则更新其值为当前索引并将”cnt0″值加1。
-
第四步 - 如果”cnt1″和”len”相等,则对二进制字符串与”1″进行异或操作,并返回其值。
-
第四步.1
-
步骤4.1.1 − 在addZero()函数中,在字符串的开头添加所需的零。
-
步骤4.2 − 初始化“XOR”字符串,以存储执行两个字符串的XOR操作后的结果。
-
步骤4.3 − 遍历两个字符串,如果两个字符串中的第p个索引处的字符相同,则将“0”附加到XOR字符串。否则,将“1”附加到XOR字符串。
-
步骤4.4 − 返回XOR字符串。
-
步骤5 - 在
maxValUtil()
函数中,如果cnt0
等于二进制字符串的长度,则返回0
。 -
步骤 6 - 使用
substr()
方法从leftZero
索引开始,将子字符串赋值给rightStr
字符串。并且,将size
初始化为rightStr
字符串的长度,temp
初始化为rightStr
字符串,maxRes
、temp1
和temp2
初始化为空字符串。 -
步骤 7 - 开始遍历二进制字符串。如果索引小于
size
变量的值,则将一个字符追加到temp1
字符串中。 -
步骤 8 - 否则,获取
temp
和temp1
字符串的 XOR 值。如果 XOR 值超过maxRes
字符串的值,则将maxRes
更新为res
,将temp2
更新为temp1
。同时,从temp1
字符串中移除第一个字符,并将当前字符追加到末尾。
这里,我们找到子字符串 ‘temp2’,使得 ‘temp1’ 与 ‘temp2’ 的异或最大化以最大化二进制字符串。
- 步骤 9 − 处理最后一种情况,其中我们将 temp1 字符串与 rightStr 字符串进行异或运算。
-
步骤 10 − 接下来,对二进制字符串和 temp2 字符串进行异或运算,并将结果存储在 answer 中。
-
步骤 11 − 在去除前导零后,返回 ‘answer’ 字符串。
示例
#include <bits/stdc++.h>
using namespace std;
void addNZero(string &substr, int n) {
// Adding the initial '0' to the string to make its length the same as the other sub string
for (int p = 0; p < n; p++) {
substr = "0" + substr;
}
}
// Finding XOR of two strings
string getXOR(string temp1, string temp2) {
// Get string sizes
int temp1_len = temp1.length();
int temp2_len = temp2.length();
// Append zeros to the smaller string
if (temp1_len > temp2_len) {
addNZero(temp2, temp1_len - temp2_len);
} else if (temp2_len > temp1_len) {
addNZero(temp1, temp2_len - temp1_len);
}
// Final string length
int len = max(temp1_len, temp2_len);
// To store the resultant XOR
string XOR = "";
// Take XOR of both strings
for (int p = 0; p < len; p++) {
if (temp1[p] == temp2[p])
XOR += "0";
else
XOR += "1";
}
return XOR;
}
string maxValUtil(string bin_str) {
// String length
int len = bin_str.size();
int leftZero = -1, cnt0 = 0, cnt1 = 0;
// Calculate number of 0's and 1's in the given string.
for (int p = 0; p < len; p++) {
if (bin_str[p] == '1') {
cnt1++;
} else {
// For the left most '0'
if (leftZero == -1) {
leftZero = p;
}
cnt0++;
}
}
// Case 1 - When the string contains all 1's
if (cnt1 == len) {
return getXOR(bin_str, "1");
}
// Case 2 - When the string contains all zeros
if (cnt0 == len) {
return "0";
}
// Take the substring starting from left most '0' as we need to maximize it
string rightStr = bin_str.substr(leftZero, len - leftZero);
int size = rightStr.size();
string temp = rightStr;
string maxRes = "";
string temp1 = "", temp2 = "";
// Choosing the second string
for (int q = 0; q < len; q++) {
// Finding the substring of length 'size' from start
if (q < size) {
temp1 += bin_str[q];
} else {
// If temp1 gives the maximum XOR result, choose it as a second string
string res = getXOR(temp, temp1);
if (res > maxRes) {
maxRes = res;
temp2 = temp1;
}
// Update temp1 string
temp1 = temp1.substr(1);
temp1 += bin_str[q];
}
}
// Handling the last case
string res = getXOR(temp1, temp);
if (res > maxRes) {
maxRes = res;
temp2 = rightStr;
}
// Take the XOR of the original string and the second string
string answer = getXOR(bin_str, temp2);
leftZero = -1;
for (int p = 0; p < answer.size(); p++) {
// Remove initial zeros
if (answer[p] != '0') {
leftZero = p;
break;
}
}
if (leftZero == -1) {
return "0";
}
// Final maximum string
return answer.substr(leftZero);
}
string findMaxValue(string bin_str, int K) {
// Find the maximum value of the updated binary string
for (int p = 0; p < K; p++) {
bin_str = maxValUtil(bin_str);
}
return bin_str;
}
int main() {
string bin_str = "1101";
int K = 1;
cout << "The maximum value of the string after performing " << K << " XOR operations is - " << findMaxValue(bin_str, K) << endl;
return 0;
}
输出
The maximum value of the string after performing 1 XOR operations is - 1111
时间复杂度 – O(NNK),其中O(N)用于找到最大化二进制字符串的子字符串,另一个O(N)用于执行两个字符串的XOR操作,O(K)用于执行总共K次操作。
空间复杂度 – O(N)用于存储临时字符串。