计算最多包含两个相邻不同字符对的 N 大小字符串的构成方法
在此问题中，我们将计算最多包含 2 个相邻不同字符对的二进制字符串的数量。这意味着该字符串最多应包含 2 个"01"或"10"对。
第一种方法是生成所有二进制字符串，如果任何二进制字符串包含少于或等于 2 个不同字符对，则将其计数包含在结果中。
对于最佳解决方案，我们可以计算包含 0、1 和 2 个相邻不同字符对的二进制字符串的数量并将它们相加。
问题陈述 - 我们给出了一个正整数 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 初始化"当前"字符串。
步骤 2 - 另外，用 0 初始化"cnt"以存储有效二进制字符串的数量，并将其作为引用参数传递给 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 ¤t, int index, int &cnt) {
// 基本情况
if (index == len) {
// 检查不同相邻字符的数量
int diff = 0;
for (int i = 0; i < len - 1; i++) {
if (current[i] != current[i + 1]) {
diff++;
}
}
if (diff <= 2) {
cnt++;
}
return;
}
// 将 '0' 放在当前索引处并进行递归调用
current[index] = '0';
getBinaryStrs(len, current, index + 1, cnt);
// 将 '1' 放在当前索引处并进行递归调用
current[index] = '1';
getBinaryStrs(len, current, index + 1, cnt);
}
void countStrings(int len) {
string current(len, '0'); // 用全"0"初始化的字符串
int cnt = 0;
getBinaryStrs(len, current, 0, cnt);
cout << "根据给定条件创建大小为 N 的字符串的方法数量为 " << cnt;
}
int main() {
int N = 3;
countStrings(N);
return 0;
}
输出
根据给定条件创建大小为 N 的字符串的方法数量为 8
时间复杂度 - O(N*2N) 生成所有二进制字符串并遍历每个字符串。
空间复杂度 - O(N) 存储长度为 N 的二进制字符串。
方法 2
在这种方法中，我们将计算长度为 N 的二进制字符串的数量，这些字符串包含最多 0、1 和 2 个相邻的不同对。我们将使用一些数学公式来获取输出。
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，在结尾有一个 1。因此，我们可以有 (N - 2) 种方法将中间的零放入字符串中。例如，从 2 开始到 N - 1，从 2 开始到 N - 2，从 2 开始到 N - 3，依此类推。
这样，我们可以从第 3 个索引开始放置 0，并且有 (N - 3) 种方法在中间放置零。
因此，在 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){
// 对所有情况的结果求和
return 2 + 2 * (len - 1) + (len - 2) * (len - 1);
}
int main(){
int N = 3;
cout << "根据给定条件创建大小为 N 的字符串的方法数量为 " << countStrings(N);
return 0;
}
输出
根据给定条件创建大小为 N 的字符串的方法数量为 8
时间复杂度 - O(1)，因为我们使用数学公式来获得答案。
空间复杂度 - O(1)，因为我们不使用任何额外空间。
第二种方法是通过执行字符串长度的乘法和求和来查找二进制字符串数量的最佳方法之一。我们根据问题陈述中的条件观察模式并准备了一个公式。
