数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装学
法学查找数组中不存在的给定大小的二进制字符串的任何排列
在这个问题中，我们需要从数组中找到所有长度为 N 的缺失二进制字符串。我们可以通过查找长度为 N 的二进制字符串的所有排列，并检查哪些排列不在数组中来解决这个问题。在这里，我们将看到解决这个问题的迭代和递归方法。
问题陈述 – 我们给定一个包含长度为 N 的二进制字符串的不同长度的数组 arr[]。我们需要找到数组中所有缺失的长度为 N 的二进制字符串。
示例
输入 – arr = {"111", "001", "100", "110"}, N = 3
输出 – [000, 010, 011, 101]
解释 – 长度为 3 的二进制字符串共有 8 个 (23 = 8)。因此，它打印长度为 3 的 4 个缺失的二进制字符串。
输入 – str = {‘00’, ‘10’, ‘11’}, N = 2
输出 – [‘01’]
解释 – 由于 ‘01’ 缺失于数组中，因此它在输出中打印。
方法 1
在这里，我们将使用迭代方法来查找长度为 N 的所有可能的二进制字符串。之后，我们将检查该字符串是否出现在数组中。如果没有，我们将打印该字符串。
算法
定义集合并使用 insert() 方法将数组中的所有字符串添加到集合中。
用 2N 初始化 total 变量，这是长度为 N 的字符串的总数。
定义 ‘cnt’ 变量并初始化为零，以存储缺失组合的总数。
使用循环进行 ‘total’ 次迭代以查找长度为 N 的所有二进制字符串。
在循环中，用空字符串初始化 ‘num’ 字符串变量。
使用嵌套循环进行总共 N 次迭代，并从最后开始迭代以创建长度为 N 的字符串。
使用 find() 方法检查集合是否包含当前字符串。如果是，则将 ‘cnt’ 的值加 1。
如果映射中不存在该字符串，则打印它以显示在输出中。
如果 ‘cnt’ 的值等于 total，则表示数组中存在所有长度为 N 的字符串，并打印“-1”。
示例
#include <bits/stdc++.h>
using namespace std;
// function to print missing combinations of a binary string of length N in an array
void printMissingCombinations(vector<string> &arr, int N) {
unordered_set<string> set;
// insert all the strings in the set
for (string temp : arr) {
set.insert(temp);
}
// get total combinations for the string of length N
int total = (int)pow(2, N);
// To store combinations that are present in an array
int cnt = 0;
// find all the combinations
for (int p = 0; p < total; p++) {
// Initialize empty binary string
string bin = "";
for (int q = N - 1; q >= 0; q--) {
// If the qth bit is set, append '1'; append '0'.
if (p & (1 << q)) {
bin += '1';
} else {
bin += '0';
}
}
// If the combination is present in an array, increment cnt
if (set.find(bin) != set.end()) {
cnt++;
continue;
} else {
cout << bin << ", ";
}
}
// If all combinations are present in an array, print -1
if (cnt == total) {
cout << "-1";
}
}
int main() {
int N = 3;
vector<string> arr = {"111", "001", "100", "110"};
printMissingCombinations(arr, N);
return 0;
}
输出
000, 010, 011, 101,
时间复杂度 – O(N*2N)，其中 O(N) 用于检查数组中是否存在字符串，O(2N) 用于查找所有可能的排列。
空间复杂度 – O(N)，因为我们使用集合来存储字符串。
方法 2
在这种方法中，我们演示了如何使用递归方法来查找长度为 N 的所有可能的二进制字符串。
算法
定义集合并将所有数组值插入集合中。
调用 generateCombinations() 函数以生成二进制字符串的所有组合。
在 generateCombinations() 函数中定义基本情况。如果索引等于 N，则将 currentCombination 推入列表中。
在将 ‘0’ 或 ‘1’ 附加到 currentCombination 后，递归调用 generateCombinations() 函数。
获得所有组合后，检查哪些组合存在于数组中，哪些组合不存在。此外，打印缺失的组合以显示在输出中。
示例
#include <bits/stdc++.h>
using namespace std;
// Function to generate all possible combinations of binary strings
void generateCombinations(int index, int N, string currentCombination, vector<string> &combinations) {
// Base case: if we have reached the desired length N, add the combination to the vector
if (index == N) {
combinations.push_back(currentCombination);
return;
}
// Recursively generate combinations by trying both 0 and 1 at the current index
generateCombinations(index + 1, N, currentCombination + "0", combinations);
generateCombinations(index + 1, N, currentCombination + "1", combinations);
}
// function to print missing combinations of a binary string of length N in an array
void printMissingCombinations(vector<string> &arr, int N) {
unordered_set<string> set;
// insert all the strings in the set
for (string str : arr) {
set.insert(str);
}
// generating all combinations of binary strings of length N
vector<string> combinations;
generateCombinations(0, N, "", combinations);
// Traverse all the combinations and check if it is present in the set or not
for (string str : combinations) {
// If the combination is not present in the set, print it
if (set.find(str) == set.end()) {
cout << str << endl;
}
}
return;
}
int main(){
int N = 3;
vector<string> arr = {"111", "001", "100", "110"};
printMissingCombinations(arr, N);
return 0;
}
输出
000 010 011 101
时间复杂度 – O(N*2N)
空间复杂度 – O(2N)，因为我们将所有组合存储在数组中。
两种方法都使用相同的逻辑来解决问题。第一种方法使用迭代技术查找长度为 N 的二进制字符串的所有组合，这比第二种方法中使用的递归技术更快。此外，第二种方法比第一种方法消耗更多的空间。
浏览量：150
