数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学给定二进制字符串的任意两个子串的最大按位或
在这个问题中，我们需要找到给定字符串的任意两个子串的最大或值。
第一种方法是找到给定二进制字符串的所有子串，取每个字符串的或值，然后打印最大或值。
另一种方法是将原始字符串作为子串，并从最左边的零开始取另一个子串以最大化或值。
问题陈述 - 我们给定一个二进制字符串alpha。我们需要找到给定二进制字符串的任意两个子串的最大或值。
示例
输入
alpha = "1000010"
输出
1100011
说明 - 第一个子串是'1000010'，另一个子串是'000010'。当我们取两者的或值时，我们得到'1100011'。
输入
alpha = "1111";
输出
1111
说明 - 字符串已经是最大的。因此，我们可以取一个原始字符串和任何其他子串来获得最大结果。
输入
alpha = "1100";
输出
1111
说明 - 我们可以取1100和11子串来获得最大结果。
方法一
在这种方法中，我们将把给定二进制字符串的所有子串存储在列表中。之后，我们将取每个子串的或值并跟踪最大值。此外，我们将创建一个函数来比较两个子串并取两个子串的或值。
算法
步骤1 - 用空字符串初始化'maxOR'字符串变量以存储任意两个字符串的最大或值。此外，定义subStr列表以存储所有子串。
步骤2 - 遍历给定的二进制字符串，使用substr()方法获取所有可能的子串，并将它们推入subStr列表。substr()方法将起始索引作为第一个参数，将子串长度作为第二个参数。
步骤3 - 开始遍历子串列表。此外，使用嵌套循环遍历所有其他子串以获取当前子串与其他子串的或值。
步骤4 - 执行takeOR()函数来获取两个字符串的或值。
步骤4.1 - 如果temp1字符串的长度较小，则在temp1字符串前面添加前导零。否则，在temp2字符串前面添加前导零。
步骤4.2 - 用空字符串初始化'res'字符串以存储结果或值。
步骤4.3 - 遍历temp1和temp2两个字符串。如果任何字符串在当前索引处包含'1'，则将'1'追加到'res'字符串。否则，将'0'追加到'res'字符串。
步骤4.4 - 返回'res'字符串。
步骤5 - 获取或值后，通过执行getmax()函数检查或值是否大于maxOR字符串的值。
步骤5.1 - 如果temp1的长度大于temp2，则返回temp1。同样，如果temp2的长度大于temp1，则返回temp1。
步骤5.2 - 开始遍历字符串。
步骤5.3 - 如果temp1中第p个索引处的字符大于temp2，则返回temp1。同样，如果temp2中第p个索引处的字符大于temp1，则返回temp2。
步骤5.4 - 最后，返回'temp1'字符串。
步骤6 - 将getMax()函数返回的值存储在'maxOR'变量中。
步骤7 - 返回'maxOR'变量的值。
示例
#include <bits/stdc++.h>
using namespace std;
string takeOR(string &temp1, string &temp2) {
// If the string length is not equal, then add 0's at the start of smaller string
if (temp1.size() < temp2.size()) {
int diff = temp2.size() - temp1.size();
for (int p = 0; p < diff; p++) {
temp1 = '0' + temp1;
}
} else if (temp1.size() > temp2.size()) {
int diff = temp1.size() - temp2.size();
for (int p = 0; p < diff; p++) {
temp2 = '0' + temp2;
}
}
string res = "";
// Take OR of both strings
for (int p = 0; p < temp1.length(); p++) {
if (temp1[p] == '1' || temp2[p] == '1') {
res += '1';
} else {
res += '0';
}
}
return res;
}
string getMax(string temp1, string temp2) {
// Return large string if the size is not equal
if (temp1.size() > temp2.size()) {
return temp1;
} else if (temp1.size() < temp2.size()) {
return temp2;
}
// Compare two strings and return the maximum string
for (int p = 0; p < temp1.size(); p++) {
if (temp1[p] > temp2[p]) {
return temp1;
} else if (temp1[p] < temp2[p]) {
return temp2;
}
}
return temp1;
}
string maxORVal(string alpha) {
string maxOR = "";
vector<string> subStr;
// get all substrings of the given string
for (int p = 0; p < alpha.length(); p++) {
for (int q = 1; q <= alpha.length() - p; q++) {
subStr.push_back(alpha.substr(p, q));
}
}
// Get the maximum OR value of two substrings
for (int p = 0; p < subStr.size(); p++) {
for (int q = p + 1; q < subStr.size(); q++) {
// Take OR of two strings
string OR_res = takeOR(subStr[p], subStr[q]);
// Get maximum string
maxOR = getMax(maxOR, OR_res);
}
}
return maxOR;
}
int main() {
string alpha = "1000010";
cout << "The maximum OR value of any two substrings of the given string is " << maxORVal(alpha);
return 0;
}
输出
The maximum OR value of any two substrings of the given string is 1100011
时间复杂度 - O(N*N*N)，其中O(N*N)用于遍历所有子串，O(N)用于查找最大值并获取两个字符串的或值。
空间复杂度 - O(N*N)用于存储所有子串。
方法二
在这种方法中，我们将取从最左边的0开始的子串，并将其与原始字符串进行或运算，这将始终给出最大值。
算法
步骤1 - 用空字符串初始化'temp1'和'temp2'字符串以存储临时字符串。
步骤2 - 接下来，我们需要从原始字符串中删除前导零。开始遍历字符串，当我们找到第一个'1'时，从该索引处获取子串，并将子串存储在'temp1'中。
步骤3 - 如果p等于字符串长度，则返回'0'，因为字符串包含所有零。
步骤4 - 开始遍历字符串，并将当前字符追加到'temp2'字符串。如果当前字符是'0'，则将索引值存储在'x'中并中断循环，因为我们需要从最左边的零开始获取子串。
步骤5 - 如果x等于'temp1'字符串的长度，则返回temp2字符串，因为它包含所有1。
步骤6 - 再次遍历字符串以获取原始字符串和从最左边的零开始的子串的或值。
步骤7 - 如果temp1[p]或temp1[x]等于'1'，则将'1'追加到temp2。否则，将'0'追加到temp2。
步骤8 - 最后，返回'temp2'字符串。
示例
#include <bits/stdc++.h>
using namespace std;
string maxORVal(string alpha) {
int p, q, len = alpha.length();
string temp1 = "", temp2 = "";
// Removing leading zeros from the string
for (p = 0; p < len; p++) {
if (alpha[p] == '1') {
// Get substring from p to len
temp1 = alpha.substr(p, len);
break;
}
}
// For a string containing all zeros, the answer is '0'.
if (p == len) {
return "0";
}
int x, temp1_len = temp1.size();
// Get substring from start to first zero
for (x = 0; x < temp1_len; x++) {
if (temp1[x] == '0') {
break;
}
temp2 += temp1[x];
}
// If the string contains all ones, the answer is '1'.
if (x == temp1_len)
return temp2;
// Get maximum OR value
for (p = 0; p < temp1_len and x < temp1_len; p++, x++) {
if (temp1[p] == '1' or temp1[x] == '1')
temp2 += '1';
else
temp2 += '0';
}
// Return the answer
return temp2;
}
int main() {
string alpha = "1000010";
cout << "The maximum OR value of any two substrings of the given string is " << maxORVal(alpha);
return 0;
}
输出
The maximum OR value of any two substrings of the given string is 1100011
时间复杂度 - O(N)用于遍历字符串一次。
空间复杂度 - O(N)用于存储子串。
第二种方法是第一种方法的优化版本。在第二种方法中，我们取从最左边的零开始的子串作为另一个子串，因为当我们将其与原始字符串进行或运算时，它总是给出最大值。
91 次查看
