C++ 计算在二进制字符串中替换’?’字符所可能的排列

在这个问题中，我们给出了一个包含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。
• 使用左移运算符得到2的cnt次方，并将其存储到’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。