C++ 计算具有最多两个相邻不同对的N个大小字符串的方法

在这个问题中，我们将计算大小为N的二进制字符串的数量，其中包含最多2个相邻不同的字符对。这意味着字符串最多应包含2个’01’或’10’对。

第一种方法是生成所有二进制字符串，并且如果任何二进制字符串包含少于或等于2个不同对的字符，则将其计数包括在结果中。

对于最优解，我们可以计算包含0、1和2个相邻不同对的二进制字符串的数量并将它们求和。

问题描述 - 我们给出了一个正整数N，表示二进制字符串的大小。我们需要计数大小为N的二进制字符串中含有最多2个相邻具有不同字符值的字符对的数量。

样例

输入

N = 3

输出

8

解释 - 所有长度为3的字符串最多包含2对相邻的不同字符。

字符串包括000、001、010、100、011、110、101、111。

输入

N = 4

输出

14

说明 — 有效的二进制字符串为 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111。我们可以观察到所有字符串最多包含2个相邻的不同对。

输入

N = 5

输出结果

22

解释 - 我们可以生成总共2^5 = 32个长度为5的二进制字符串，但只有22个根据问题中给定的条件是有效的。

有效的二进制字符串是00000, 00001, 00010, 00011, 00100, 00101, 00110, 00111, 01000, 01001, 01010, 01011, 01100, 01101, 01110, 01111, 10000, 10001, 10010, 10011, 10100, 10101, 10110, 10111, 11000, 11001, 11010, 11011, 11100, 11101, 11110, 11111.

方法1

在这个方法中，我们将使用递归函数来生成所有的二进制字符串。对于每个二进制字符串，我们检查其中包含的不同相邻对的数量。如果小于3，我们会增加结果计数的值。

算法

步骤1 - 使用N个0初始化’current’字符串。

步骤2 - 同样，初始化’cnt’为0以存储有效二进制字符串的计数，并将其作为引用参数传递给getBinaryStr()函数。

步骤3 - 在getBinaryStr()函数中，如果索引等于字符串长度，我们获取二进制字符串并按照下面的步骤计算不同相邻对的数量。

步骤3.1 - 使用0初始化’diff’变量以存储相邻不同对的数量。

步骤3.2 - 开始遍历字符串，如果第i和(i + 1)个索引处的字符不相同，则将’diff’值增加1。

步骤3.3 - 遍历字符串后，如果’diff’值小于或等于2，则将’cnt’值增加1，并执行’return’语句。

步骤3.4 - 在当前索引处插入’0’，并通过将索引值增加1来进行递归函数调用。

步骤3.5 - 在当前索引处插入’1’，并通过将索引值增加1来进行递归函数调用。

步骤4 - 在countStrings()函数中，打印’cnt’值。

示例

#include <bits/stdc++.h>
using namespace std;

void getBinaryStrs(int len, string &current, int index, int &cnt) {
    // Base case
    if (index == len) {
        // Checking the number of different adjacent characters
        int diff = 0;
        for (int i = 0; i < len - 1; i++) {
            if (current[i] != current[i + 1]) {
                diff++;
            }
        }
        if (diff <= 2) {
            cnt++;
        }
        return;
    }
    // Put '0' at the current index and make a recursive call
    current[index] = '0';
    getBinaryStrs(len, current, index + 1, cnt);
    // Put '1' at the current index and make a recursive call
    current[index] = '1';
    getBinaryStrs(len, current, index + 1, cnt);
}
void countStrings(int len) {
    string current(len, '0'); // String initialized with all '0's
    int cnt = 0;
    getBinaryStrs(len, current, 0, cnt);
    cout << "The number of ways to create a string of size N according to the given conditions is " << cnt;
}
int main() {
    int N = 3;
    countStrings(N);
    return 0;
}

输出

The number of ways to create a string of size N according to the given conditions is 8

时间复杂度 – O(N*2N) 用于生成所有二进制字符串并遍历每个字符串。

空间复杂度 – O(N) 用于存储长度为N的二进制字符串。

方法2

在这个方法中，我们将计算长度为N的二进制字符串中包含最多0、1和2个相邻不同对的数量。我们将使用一些数学公式来得到输出。

0个相邻对包含不同字符

我们只能构造出两个不含有不同相邻值对的二进制字符串。第一个包含全0，第二个包含全1。

1个相邻对包含不同字符

对于包含不同字符的1个相邻对，我们在结果字符串中只能有一个01或者10对。所以，对于长度为N的字符串，我们可以有2*(N – 1)个选择。

在这里，2表示的是10和01对，(N – 1)表示字符串中1和0的不同数量。例如，对于N = 4，我们可以构造0111、0011、0001，总共3个(4 – 1)包含’01’对的字符串。同样，我们还可以构造另外3个只包含’10’对一次的字符串。

2个相邻对包含不同字符

对于包含2个相邻不同字符对的字符串，我们可以有010和101两种模式。

对于’101’模式，我们始终需要在开头和结尾处各有一个1。所以，我们在字符串中放置中间的0的方式有(N – 2)种。例如，从2到N – 1，2到N – 2，2到N – 3，依此类推。

这样，我们可以从第3个索引开始放置0，并在中间有(N – 3)种放0的方式。

所以，将0放入101模式中的方式总共有(N – 2) + (N – 3) + (N – 4) + … + 2 + 1，也就是(N – 2) * (N – 1) /2。这里，我们使用了(a) * (a + 1)/2的求和公式，表示1 + 2 + 3 + … + (a – 1) + a的和。

我们还需要计算包含010模式的字符串数量。所以，所需的二进制字符串的总数为2(N – 2)(N – 1)/2，也就是(N – 1)*(N – 2)。

我们的最终公式来获取所有有效子字符串如下所示。

2 + 2 * (len – 1) + (len – 2) * (len – 1)

示例

在这个示例中，我们使用上面的公式计算了二进制字符串的数量，其中最多有2个相邻对具有不同的值。

#include <bits/stdc++.h>
using namespace std;

long long countStrings(long long len){
   // Sum results of all cases
   return 2 + 2 * (len - 1) + (len - 2) * (len - 1);
}
int main(){
   int N = 3;
   cout << "The number of ways to create a string of size N according to the given conditions is " << countStrings(N);
   return 0;
}

输出

The number of ways to create a string of size N according to the given conditions is 8

时间复杂度 – O(1)，因为我们使用数学公式来获得答案。

空间复杂度 – O(1)，因为我们不使用任何额外的空间。

第二种方法是通过对字符串长度进行乘法和求和来找到二进制字符串的数量的最佳方法。我们根据问题陈述中的条件观察到了模式，并准备了一个公式。