計算二進位制字串中替換“？”字元可能產生的排列數

---

在這個問題中，我們給定一個包含 0、1 和“？”字元的字串。我們需要透過用 0 和 1 替換“？”來找到字串的排列。解決問題的邏輯是，我們可以用 0 或 1 替換每個“？”。因此，透過替換一個“？”，我們可以生成兩個不同的排列，並且透過用 2 種可能性替換 N 個“？”，我們可以生成 2^N 個排列。

在本教程中，我們將學習兩種不同的方法來解決給定的問題。

問題陳述 – 我們給定一個包含“0”、“1”和“？”字元的字串 str。我們需要用 0 或 1 替換“？”並找到給定字串的所有排列。

示例

輸入 – str = "0101001??01"

輸出 – 4

解釋 – 4 個不同的組合是 01010010101、01010011001、01010010001 和 01010011101

輸入 – str = ’01?0’

輸出 – 2

解釋 – 2 個不同的組合是 0100 和 0110。

輸入 – str = ‘01010’

輸出 – 1

解釋 – 給定的字串本身就是一個排列。

方法 1

在這種方法中，我們將透過遍歷字串來計算給定字串中“？”的總數。之後，我們將使用左移運算子獲取 2^N，其中 N 是字串中“？”的總數。

演算法

• 定義變數“cnt”並初始化為 0，以儲存給定字串中“？”的數量

• 使用迴圈遍歷字串。如果當前字元是“？”，則將“cnt”變數的值增加 1。

• 使用左移運算子獲取 2cnt 並將其儲存到“perm”變數中。

• 返回“perm”變數的值

示例

#include <iostream>
using namespace std;

// function to count the number of permutations of the given string by replacing '?' with '0' or '1'
int totalPermutations(string s){
   // variable to store the count of '?' in the string
   int cnt = 0;
   // loop to count the number of '?' in the string
   for (int i = 0; i < s.length(); i++){
      if (s[i] == '?'){
         cnt++;
      }
   }
   // total number of permutations of the string by replacing'?' with '0' or '1' is 2^cnt
   int perm = 0;
   //   calculating 2^cnt with left shift operator
   perm = 1 << cnt;
   return perm;
}
int main(){
   string str = "0101001??01";
   cout << "The total number of permutations of the string we can get by replacing ? with 0 or 1 is " << totalPermutations(str);
   return 0;
}

輸出

The total number of permutations of the string we can get by replacing ? with 0 or 1 is 4

時間複雜度 – O(N)，因為我們遍歷了字串。

空間複雜度 – O(1)，因為我們沒有使用動態空間。

方法 2

在這種方法中，我們將使用 count() 方法來計算給定字串中“？”字元的總數。之後，我們使用 pow() 方法計算 2^N。

演算法

• 定義變數“cnt”並將其初始化為零。

• 使用 count() 方法計算給定字串中“？”出現的總數。我們需要將字串的起始點作為第一個引數，結束點作為第二個引數，以及“？”作為第三個引數傳遞。

• 使用 pow() 方法獲取 2cnt。

• 返回“perm”值。

示例

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

// function to count the number of permutations of the given string by replacing '?' with '0' or '1'
int totalPermutations(string s){
   // variable to store the count of '?' in the string
   int cnt = 0;
   //    using the count() function to count the number of '?' in the string
   cnt = count(s.begin(), s.end(), '?');
   int perm = 0;
   //   calculating 2^cnt using the pow() function
   perm = pow(2, cnt);
   return perm;
}
int main(){
   string str = "0101001??01";
   cout << "The total number of permutations of the string we can get by replacing ? with 0 or 1 is " << totalPermutations(str);
   return 0;
}

輸出

The total number of permutations of the string we can get by replacing ? with 0 or 1 is 4

時間複雜度 – O(N)，因為 count() 方法迭代長度為 N 的字串。

空間複雜度 – O(1)

我們學習了兩種不同的方法來計算透過用 0 或 1 替換“？”字元可以獲得的排列總數。程式設計師可以使用左移運算子的 pow() 方法來計算 2N。