資料結構
網路
關係資料庫管理系統 (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 次檢視
