数据结构
网络
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 次浏览
启动您的立即开始
