数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学统计最多只有两个相邻不同对的 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
解释 - 我们可以生成长度为 5 的 2^5 = 32 个二进制字符串，但根据问题中给出的条件，只有 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。
方法一
在这种方法中，我们将使用递归函数来生成所有二进制字符串。对于每个二进制字符串，我们检查它包含多少个相邻的不同对。如果少于 3 个，我们将结果计数值加 1。
算法
步骤 1 - 用 N 个 0 初始化 'current' 字符串。
步骤 2 - 还将 'cnt' 初始化为 0 以存储有效二进制字符串的计数，并将其作为引用参数传递到 getBinaryStr() 函数中。
步骤 3 - 在 getBinaryStr() 函数中，如果索引等于字符串长度，我们将获得二进制字符串，并按照以下步骤计算相邻不同对的数量。
步骤 3.1 - 将 'diff' 变量初始化为 0 以存储相邻不同对的数量。
步骤 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) {
// 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 的二进制字符串。
方法二
在这种方法中，我们将计算长度为 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。因此，我们可以有 (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。在这里，我们使用了 1 + 2 + 3 + … + (a - 1) + a 级数的 (a) * (a + 1)/2 公式。
我们还需要计算包含 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)，因为我们不使用任何额外的空间。
第二种方法是通过执行字符串长度的乘法和求和来查找二进制字符串计数的最佳方法之一。我们根据问题陈述中的条件观察到了模式，并制定了一个公式。
120 次查看
