Cari sebarang pilihatur yang tidak wujud dalam tatasusunan rentetan binari saiz tertentu

Dalam masalah ini, kita perlu mencari semua rentetan binari panjang N yang hilang daripada tatasusunan. Kita boleh menyelesaikan masalah ini dengan mencari semua pilih atur rentetan binari panjang N dan menyemak pilih atur yang tidak wujud dalam tatasusunan. Di sini kita akan melihat kaedah berulang dan rekursif untuk menyelesaikan masalah ini.

Pernyataan Masalah - Kami telah diberikan array arr[] panjang N yang mengandungi rentetan binari dengan panjang yang berbeza. Kita perlu mencari semua rentetan binari panjang N yang hilang daripada tatasusunan.

Contoh Contoh

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

Output – [000, 010, 011, 101]

Penjelasan – Terdapat 8 rentetan binari dengan panjang 3, kerana 2 dinaikkan kepada kuasa ketiga adalah bersamaan dengan 8. Jadi, ia mencetak 4 rentetan binari panjang 3 yang hilang.

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

Output –[‘01’]

Penjelasan – '01' tiada dalam tatasusunan, jadi ia akan dicetak dalam output.

Kaedah 1

Di sini, kami akan menggunakan kaedah lelaran untuk mencari semua kemungkinan rentetan binari panjang N. Selepas itu kami akan menyemak sama ada rentetan itu wujud dalam tatasusunan. Jika ia tidak wujud, kami mencetak rentetan.

Algoritma

• Tentukan koleksi dan gunakan kaedah insert() untuk menambah semua rentetan dalam tatasusunan pada koleksi.

• Mulakan jumlah pembolehubah dengan 2N, di mana 2N ialah jumlah bilangan rentetan panjang N

• Tentukan 'cnt' pembolehubah dan mulakannya kepada sifar untuk menyimpan jumlah gabungan yang hilang.

• Gunakan gelung untuk membuat 'jumlah' bilangan lelaran untuk mencari semua rentetan binari panjang N.

• Dalam gelung, mulakan pembolehubah rentetan "num" dengan rentetan kosong.

• Gunakan gelung bersarang untuk sejumlah N lelaran dan bermula dari lelaran terakhir, buat rentetan panjang N.

• Gunakan kaedah find() untuk menyemak sama ada koleksi mengandungi rentetan semasa. Jika ya, tingkatkan nilai 'cnt' sebanyak 1.

• Jika rentetan tiada dalam peta, cetak untuk ditunjukkan dalam output

• Jika nilai "cnt" adalah sama dengan jumlah nombor, ini bermakna semua rentetan panjang N wujud dalam tatasusunan dan "-1" dicetak.

Contoh

#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;
}

Output

000, 010, 011, 101, 

Kerumitan masa - O(N*2N), di mana O(N) digunakan untuk menyemak sama ada rentetan wujud dalam tatasusunan dan O(2N) digunakan untuk mencari semua pilih atur yang mungkin.

Kerumitan ruang - O(N) kerana kami menggunakan set untuk menyimpan rentetan.

Kaedah 2

Dalam kaedah ini, kami menunjukkan menggunakan kaedah rekursif untuk mencari semua kemungkinan rentetan binari panjang N.

Algoritma

• Tentukan koleksi dan masukkan semua nilai tatasusunan ke dalam koleksi.

• Panggil fungsi generateCombinations() untuk menjana semua kombinasi rentetan binari

• Tentukan kes asas dalam fungsi generateCombinations(). Jika indeks adalah sama dengan N, maka currentCombination ditambahkan pada senarai.

• Selepas menambah '0' atau '1' pada gabungan semasa, panggil fungsi generateCombinations() secara rekursif.

• Selepas mendapat semua kombinasi, semak kombinasi yang mana terdapat dalam tatasusunan dan yang mana tidak. Juga, cetak kombinasi yang hilang untuk ditunjukkan dalam output.

Contoh

#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;
}

Output

000
010
011
101

Kerumitan masa - O(N*2N)

Kerumitan ruang - O(2N) kerana kami menyimpan semua kombinasi dalam tatasusunan.

Kedua-dua kaedah menggunakan logik yang sama untuk menyelesaikan masalah. Kaedah pertama menggunakan teknik berulang untuk mencari semua kombinasi rentetan binari panjang N, yang lebih cepat daripada teknik rekursif yang digunakan dalam kaedah kedua. Juga, kaedah kedua menggunakan lebih banyak ruang daripada kaedah pertama.

Atas ialah kandungan terperinci Cari sebarang pilihatur yang tidak wujud dalam tatasusunan rentetan binari saiz tertentu. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!