找到給定大小的二進位字串陣列中不存在的任意排列

在這個問題中，我們需要從陣列中找到長度為N的所有缺失的二進位字串。我們可以透過找到長度為N的二進位字串的所有排列，並檢查哪些排列在陣列中不存在來解決這個問題。在這裡，我們將看到迭代和遞歸的方法來解決這個問題。

問題陳述 - 我們已經給了一個包含不同長度的二進位字串的陣列arr[]，長度為N。我們需要從陣列中找出所有長度為N的缺失二進位字串。

範例範例

輸入 – arr = {"111", "001", "100", "110"}, N = 3

輸出 – [000, 010, 011, 101]

Explanation – 有8個長度為3的二進位字串，因為2的3次方等於8。所以，它印出長度為3的缺失的4個二進位字串。

輸入 – str = {‘00’, ‘10’, ‘11’}, N = 2

Output – [‘01’]

Explanation – ‘01’在陣列中缺失，因此會在輸出中列印出來。

方法一

在這裡，我們將使用迭代的方法來找到長度為N的所有可能的二進位字串。之後，我們將檢查該字串是否存在於數組中。如果不存在，我們將列印該字串。

演算法

• 定義集合並使用insert()方法將陣列中的所有字串加入集合。

• 用2N初始化total變量，其中2N是長度為N的字串的總數

• #定義變數 'cnt' 並將其初始化為零，以儲存缺失組合的總數。

• 使用循環來使'總'迭代次數，以找到所有長度為N的二進位字串。

• 在迴圈中，使用空字串初始化「num」字串變數。

• 使用巢狀循環進行總共N次迭代，並從最後一次迭代開始，建立長度為N的字串。

• 使用find()方法來檢查集合是否包含目前字串。如果是，則將‘cnt’的值增加1。

• 如果字串不在映射中，則列印它以顯示在輸出中

• 如果「cnt」的值等於總數，則表示陣列中存在所有長度為N的字串，並列印「-1」。

Example

#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)，因為我們使用set來儲存字串。

方法二

在這個方法中，我們展示了使用遞歸方法來找到長度為N的所有可能的二進位字串。

演算法

• 定義集合並將所有陣列值插入集合中。

• 呼叫generateCombinations()函數產生二進位字串的所有組合

• 在generateCombinations()函數中定義基本情況。如果索引等於N，則將currentCombination新增至清單。

• 在將‘0’或‘1’新增至目前組合後，遞歸呼叫generateCombinations()函數。

• 取得所有組合後，檢查哪些組合存在於陣列中，哪些不存在。同時，列印出缺失的組合以在輸出中顯示。

Example

#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的二進位字串的所有組合，比第二種方法中使用的遞歸技術更快。此外，第二種方法消耗的空間比第一種方法多。

以上是找到給定大小的二進位字串陣列中不存在的任意排列的詳細內容。更多資訊請關注PHP中文網其他相關文章！