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