資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
安卓
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究找到所有包含偶數個 1 且其反轉也出現在給定字串中的子字串
在這個問題中，我們需要準備給定二進位制字串的一組唯一子字串，如果它們包含偶數個 1 且它們的逆序也存在於該組中，則將它們從該組中刪除。
我們可以用兩種方法來解決這個問題。第一種方法是找到給定二進位制字串的所有子字串，檢查任何子字串是否包含偶數個 1 以及它的逆序是否存在，並將逆序字串從該組中刪除。
另一種方法是比較給定字串中奇偶校驗位的總數。
問題陳述 - 我們給出了包含偶數個 1 的二進位制字串 str。我們需要準備給定二進位制字串的所有唯一子字串的集合。之後，我們需要考慮從集合中包含偶數個 1 的長度為 n 的子字串。如果子字串的逆序也存在於該集合中，則從該集合中刪除逆序子字串。在輸出中，列印包含唯一子字串的集合的大小。
樣例
輸入
str = "01010"
輸出
8
解釋
唯一子字串的集合為 [0, 1, 01, 010, 0101, 01010, 10, 101, 1010]。它總共包含 9 個子字串。
0101 包含偶數個 1，並且它的逆序也存在於該集合中。因此，我們將從給定集合中刪除它的逆序，即 1010。
最終集合為 [0, 1, 01, 010, 0101, 01010, 10, 101]。最終集合的大小為 8。
輸入
str = '1010'
輸出
7
解釋
唯一子字串為 [ 1, 10, 101, 1010, 0, 01, 010]。
對於任何包含偶數個 1 的字串，其反向不在集合中。因此，我們不需要從集合中移除任何字串。
最終輸出與原始集合的大小相同。
輸入
str = "111"
輸出
3
唯一子字串為 [1, 11, 111]。
包含偶數個 1 的字串只有 11。
11 的反向也是 11。因此，我們不需要從集合中移除它，答案為 3。
方法 1
在此方法中，我們將建立一個集合，其中包含給定二進位制字串的所有唯一子字串。之後，我們將遍歷集合，如果我們發現包含偶數個 1 的字串及其反向也存在於集合中，則我們將從集合中移除該字串。
演算法
步驟 1 - 定義名為 'subStrings' 的集合以儲存唯一子字串。
步驟 2 - 從第 0 個索引開始遍歷字串。在迴圈內，定義 'temp' 變數並用空字串初始化。
步驟 3 - 使用另一個巢狀迴圈從 pth 索引開始迭代，並不斷將 qth 字元附加到 'temp' 字串。
步驟 4 - 將 'temp' 字串插入集合。
步驟 5 - 使用迭代器遍歷子字串集合。
步驟 7 - 如果當前字串中的 1 的總數是偶數，則反轉 temp 字串，並檢查集合中是否存在反向 temp。
步驟 8 - 如果存在反向字串，則移除該反向字串。
步驟 9 - 返回集合的大小。
示例
#include <bits/stdc++.h>
using namespace std;
int getSize(string str) {
// unordered set to store all substrings of a given string
unordered_set<string> subStrings;
// finding all substrings of a given string
for (int p = 0; p < str.length(); p++) {
string temp = "";
for (int q = p; q < str.length(); q++) {
temp += str[q];
subStrings.insert(temp);
}
}
// Check if any string contains an even number of 1's and its reverse exists in the set, then remove the string.
for (auto it = subStrings.begin(); it != subStrings.end(); it++) {
string temp = *it;
// count the number of 1's in the string
int cnt1s = 0;
for (int i = 0; i < temp.length(); i++) {
if (temp[i] == '1')
cnt1s++;
}
// If count of 1's is even
if (cnt1s % 2 == 0) {
// reverse substring
reverse(temp.begin(), temp.end());
// check if reverse exists in the set, remove it.
if (temp != *it && subStrings.find(temp) != subStrings.end()) {
subStrings.erase(temp);
}
}
}
return subStrings.size();
}
int main() {
string str = "01010";
cout << "The size of the set containing unique strings is " << getSize(str);
return 0;
}
輸出
The size of the set containing unique strings is 8
時間複雜度 - O(N^4)，因為 O(N^2) 用於遍歷所有子字串的集合，並且我們使用巢狀迴圈來遍歷該集合。
空間複雜度 - O(N^2) 用於在集合中儲存所有子字串。
方法 2
在此方法中，我們將建立一個包含 3 個引數的列表：子字串長度、偶數個 1 和奇數個 1。字串的反向也將具有相同的長度、偶數個 1 和奇數個 1。如果我們將唯一對新增到列表，我們可以找到所有可以遵循列表條件的子字串。
演算法
步驟 1 - 定義向量集合 'setList'
步驟 2 - 開始遍歷字串。此外，定義 cnt1s、even1s 和 odd1s 變數並用零初始化。
步驟 3 - 開始遍歷子字串。如果 qth 索引處的字元為 '1'，則將 cnt1s 增加 1。
步驟 4 - 否則，如果 cnt1s 為偶數，則增加 even1s。否則，增加 odd1s。
步驟 5 - 獲取子字串的長度，並在建立列表後在集合中儲存 len、even1s 和 odd1s。
步驟 6 - 返回列表的大小。
示例
#include <bits/stdc++.h>
using namespace std;
int getSize(string str) {
// set to store the unique strings
set<vector<int>> setList;
// Iterate the string
for (int p = 0; p < str.length(); p++) {
// Required variables
int cnt1s = 0, even1s = 0, odd1s = 0;
for (int q = p; q < str.length(); q++) {
// Count the counts of 1's
if (str[q] == '1') {
cnt1s++;
} else {
// If the count of 1's is even, increment even1s. Otherwise, increment odd1s.
if (cnt1s % 2 == 0) {
even1s++;
} else {
odd1s++;
}
}
// get substring length
int len = q - p + 1;
// Insert the substring in the set
vector<int> temp;
temp.push_back(len);
temp.push_back(even1s);
temp.push_back(odd1s);
setList.insert(temp);
}
}
return setList.size();
}
int main() {
string str = "01010";
cout << "The size of the set containing unique strings is " << getSize(str);
return 0;
}
輸出
The size of the set containing unique strings is 8
時間複雜度 - O(N^2)，因為我們建立了所有子字串。
空間複雜度 - O(N*N) 用於在集合中儲存對。
對於初學者來說，第二種解決方案可能有點難以理解，但是如果我們說反向字串具有相同的長度和奇偶校驗位，那麼它就很容易理解。第一種方法的時間複雜度要高得多。因此，最好使用第二種方法解決問題。
85 次瀏覽
啟動您的立即開始
