本文概述

• C ++
• Java
• Python3
• C#
• C ++
• Java
• Python3
• C#

给定三个整数N, P和问, 任务是计算所有可能的不同长度的二进制字符串N这样每个二进制字符串都不包含P连续0次且问连续1次。
例子：

输入：N = 5, P = 2, Q = 3
输出：7
说明：满足给定条件的二进制字符串为{" 01010", " 01011", " 01101", " 10101", " 10110", " 11010" , " 11011"}。
因此, 所需的输出为7。
输入：N = 5, P = 3, Q = 4
输出：21

简单的方法：这个问题可以用解决递归。以下是递归关系及其基本情况：

在二进制字符串的每个可能索引处, 要么放置值" 0", 要么放置值" 1"。因此, cntBinStr(str, N, P, Q)= cntBinStr(str +'0', N, P, Q) + cntBinStr(str +'1', N, P, Q), 其中cntBinStr(str, N, P, Q)存储不包含P个连续1和Q个连续0的不同二进制字符串的计数。基本情况：如果length(str)== N, 请检查str是否满足给定条件。如果发现为真, 则返回1。否则, 返回0。

下面是上述方法的实现：
C ++

//C++ program to implement //the above approach #include < bits/stdc++.h> using namespace std; //Function to check if a //string satisfy the given //condition or not bool checkStr(string str, int P, int Q) { //Stores the length //of string int N = str.size(); //Stores the previous //character of the string char prev = str[0]; //Stores the count of //consecutive equal characters int cnt = 0; //Traverse the string for ( int i = 0; i < N; i++) { //If current character //is equal to the //previous character if (str[i] == prev) { cnt++; } else { //If count of consecutive //1s is more than Q if (prev == '1' & & cnt> = Q) { return false ; } //If count of consecutive //0s is more than P if (prev == '0' & & cnt> = P) { return false ; } //Reset value of cnt cnt = 1; } prev = str[i]; } //If count of consecutive //1s is more than Q if (prev == '1' & & cnt> = Q) { return false ; } //If count of consecutive //0s is more than P if (prev == '0' & & cnt> = P) { return false ; } return true ; } //Function to count all distinct //binary strings that satisfy //the given condition int cntBinStr(string str, int N, int P, int Q) { //Stores the length of str int len = str.size(); //If length of str is N if (len == N) { //If str satisfy //the given condition if (checkStr(str, P, Q)) return 1; //If str does not satisfy //the given condition return 0; } //Append a character '0' at //end of str int X = cntBinStr(str + '0' , N, P, Q); //Append a character '1' at //end of str int Y = cntBinStr(str + '1' , N, P, Q); //Return total count //of binary strings return X + Y; } //Driver Code int main() { int N = 5, P = 2, Q = 3; cout < < cntBinStr( "" , N, P, Q); return 0; }

Java

//Java program to implement //the above approach class GFG{//Function to check if a //string satisfy the given //condition or not static boolean checkStr(String str, int P, int Q) {//Stores the length //of string int N = str.length(); //Stores the previous //character of the string char prev = str.charAt( 0 ); //Stores the count of //consecutive equal characters int cnt = 0 ; //Traverse the string for ( int i = 0 ; i < N; i++) {//If current character //is equal to the //previous character if (str.charAt(i) == prev) { cnt++; } else {//If count of consecutive //1s is more than Q if (prev == '1' & & cnt> = Q) { return false ; }//If count of consecutive //0s is more than P if (prev == '0' & & cnt> = P) { return false ; }//Reset value of cnt cnt = 1 ; } prev = str.charAt(i); }//If count of consecutive //1s is more than Q if (prev == '1' & & cnt> = Q) { return false ; }//If count of consecutive //0s is more than P if (prev == '0' & & cnt> = P) { return false ; } return true ; }//Function to count all distinct //binary strings that satisfy //the given condition static int cntBinStr(String str, int N, int P, int Q) {//Stores the length of str int len = str.length(); //If length of str is N if (len == N) {//If str satisfy //the given condition if (checkStr(str, P, Q)) return 1 ; //If str does not satisfy //the given condition return 0 ; }//Append a character '0' at //end of str int X = cntBinStr(str + '0' , N, P, Q); //Append a character '1' at //end of str int Y = cntBinStr(str + '1' , N, P, Q); //Return total count //of binary strings return X + Y; }//Driver Code public static void main (String[] args) { int N = 5 , P = 2 , Q = 3 ; System.out.println(cntBinStr( "" , N, P, Q)); } } //This code is contributed by code_hunt

Python3

# Python3 program to implement # the above approach # Function to check if a # satisfy the given # condition or not def checkStr( str , P, Q):# Stores the lenngth # of string N = len ( str ) # Stores the previous # character of the string prev = str [ 0 ] # Stores the count of # consecutive equal # characters cnt = 0 # Traverse the string for i in range (N):# If current character # is equal to the # previous character if ( str [i] = = prev): cnt + = 1 else :# If count of consecutive # 1s is more than Q if (prev = = '1' and cnt> = Q): return False # If count of consecutive # 0s is more than P if (prev = = '0' and cnt> = P): return False # Reset value of cnt cnt = 1 prev = str [i] # If count of consecutive # 1s is more than Q if (prev = = '1' and cnt> = Q): return False # If count of consecutive # 0s is more than P if (prev = = '0' and cnt> = P): return False return True # Function to count all # distinct binary strings # that satisfy the given # condition def cntBinStr( str , N, P, Q):# Stores the length # of str lenn = len ( str ) # If lenngth of str # is N if (lenn = = N): # If str satisfy # the given condition if (checkStr( str , P, Q)): return 1 # If str does not satisfy # the given condition return 0 # Append a character '0' # at end of str X = cntBinStr( str + '0' , N, P, Q) # Append a character # '1' at end of str Y = cntBinStr( str + '1' , N, P, Q) # Return total count # of binary strings return X + Y # Driver Code if __name__ = = '__main__' :N = 5 P = 2 Q = 3 print (cntBinStr("", N, P, Q)) # This code is contributed by mohit kumar 29

C#

//C# program to implement //the above approach using System; class GFG{//Function to check if a //string satisfy the given //condition or not static bool checkStr( string str, int P, int Q) {//Stores the length //of string int N = str.Length; //Stores the previous //character of the string char prev = str[0]; //Stores the count of //consecutive equal characters int cnt = 0; //Traverse the string for ( int i = 0; i < N; i++) {//If current character //is equal to the //previous character if (str[i] == prev) { cnt++; } else {//If count of consecutive //1s is more than Q if (prev == '1' & & cnt> = Q) { return false ; }//If count of consecutive //0s is more than P if (prev == '0' & & cnt> = P) { return false ; }//Reset value of cnt cnt = 1; }prev = str[i]; }//If count of consecutive //1s is more than Q if (prev == '1' & & cnt> = Q) { return false ; }//If count of consecutive //0s is more than P if (prev == '0' & & cnt> = P) { return false ; }return true ; }//Function to count all distinct //binary strings that satisfy //the given condition static int cntBinStr( string str, int N, int P, int Q) {//Stores the length of str int len = str.Length; //If length of str is N if (len == N) {//If str satisfy //the given condition if (checkStr(str, P, Q)) return 1; //If str does not satisfy //the given condition return 0; }//Append a character '0' at //end of str int X = cntBinStr(str + '0' , N, P, Q); //Append a character '1' at //end of str int Y = cntBinStr(str + '1' , N, P, Q); //Return total count //of binary strings return X + Y; }//Driver Code public static void Main () { int N = 5, P = 2, Q = 3; Console.WriteLine(cntBinStr( "" , N, P, Q)); } } //This code is contributed by sanjoy_62

输出如下

7

时间复杂度：
【计算可能的长度为N的二进制字符串，而没有P个连续的0和Q个连续的1】O(2
N
)
辅助空间：
O(1)
高效方法：为了优化上述方法, 想法是使用动态编程。请按照以下步骤解决问题：

• 初始化两个2D 数组说零[N] [P]和一个[N] [Q].
• 零[i] [j]存储长度为二??进制的字符串的计数一世有?连续0。填满所有的值零[i] [j]以自下而上的方式。

在第i个索引处插入0。情况1：如果字符串的第(i – 1)个索引包含1。情况2：如果字符串[i – 1]的第i个索引包含0。对于[2, P – 1]范围内的所有r。

• 一个[i] [j]存储长度为二??进制的字符串的计数一世有?连续1个。以自下而上的方式填充所有零[i] [j]的值。

在第i个索引处插入1。情况1：如果字符串的第(i-1)个索引包含0, 则情况2：如果字符串[i-1]的第i-1个索引包含1, 则对于[2, Q – 1]范围内的所有j。

• 最后, 打印满足给定条件的子数组的计数。

C ++

//C++ program to implement //the above approach #include < bits/stdc++.h> using namespace std; //Function to count binary strings //that satisfy the given condition int cntBinStr( int N, int P, int Q) { //zero[i][j] stores count //of binary strings of length i //having j consecutive 0s int zero[N + 1][P]; //one[i][j] stores count //of binary strings of length i //having j consecutive 1s int one[N + 1][Q]; //Set all values of //zero[][] array to 0 memset (zero, 0, sizeof (zero)); //Set all values of //one[i][j] array to 0 memset (one, 0, sizeof (one)); //Base case zero[1][1] = one[1][1] = 1; //Fill all the values of zero[i][j] //and one[i][j] in bottom up manner for ( int i = 2; i < = N; i++) { for ( int j = 2; j < P; j++) { zero[i][j] = zero[i - 1][j - 1]; } for ( int j = 1; j < Q; j++) { zero[i][1] = zero[i][1] + one[i - 1][j]; } for ( int j = 2; j < Q; j++) { one[i][j] = one[i - 1][j - 1]; } for ( int j = 1; j < P; j++) { one[i][1] = one[i][1] + zero[i - 1][j]; } } //Stores count of binary strings //that satisfy the given condition int res = 0; //Count binary strings of //length N having less than //P consecutive 0s for ( int i = 1; i < P; i++) { res = res + zero[N][i]; } //Count binary strings of //length N having less than //Q consecutive 1s for ( int i = 1; i < Q; i++) { res = res + one[N][i]; } return res; } //Driver Code int main() { int N = 5, P = 2, Q = 3; cout < < cntBinStr(N, P, Q); return 0; }

Java

//Java program to implement //the above approach import java.util.*; class GFG{ //Function to count binary Strings //that satisfy the given condition static int cntBinStr( int N, int P, int Q) {//zero[i][j] stores count //of binary Strings of length i //having j consecutive 0s int [][]zero = new int [N + 1 ][P]; //one[i][j] stores count //of binary Strings of length i //having j consecutive 1s int [][]one = new int [N + 1 ][Q]; //Base case zero[ 1 ][ 1 ] = one[ 1 ][ 1 ] = 1 ; //Fill all the values of zero[i][j] //and one[i][j] in bottom up manner for ( int i = 2 ; i < = N; i++) { for ( int j = 2 ; j < P; j++) { zero[i][j] = zero[i - 1 ][j - 1 ]; } for ( int j = 1 ; j < Q; j++) { zero[i][ 1 ] = zero[i][ 1 ] + one[i - 1 ][j]; } for ( int j = 2 ; j < Q; j++) { one[i][j] = one[i - 1 ][j - 1 ]; } for ( int j = 1 ; j < P; j++) { one[i][ 1 ] = one[i][ 1 ] + zero[i - 1 ][j]; } } //Stores count of binary Strings //that satisfy the given condition int res = 0 ; //Count binary Strings of //length N having less than //P consecutive 0s for ( int i = 1 ; i < P; i++) { res = res + zero[N][i]; } //Count binary Strings of //length N having less than //Q consecutive 1s for ( int i = 1 ; i < Q; i++) { res = res + one[N][i]; } return res; } //Driver Code public static void main(String[] args) { int N = 5 , P = 2 , Q = 3 ; System.out.print(cntBinStr(N, P, Q)); } } //This code is contributed by Amit Katiyar

Python3

# Python3 program to implement # the above approach # Function to count binary # Strings that satisfy the # given condition def cntBinStr(N, P, Q):# zero[i][j] stores count # of binary Strings of length i # having j consecutive 0s zero = [[ 0 for i in range (P)] for j in range (N + 1 )]; # one[i][j] stores count # of binary Strings of length i # having j consecutive 1s one = [[ 0 for i in range (Q)] for j in range (N + 1 )]; # Base case zero[ 1 ][ 1 ] = one[ 1 ][ 1 ] = 1 ; # Fill all the values of # zero[i][j] and one[i][j] # in bottom up manner for i in range ( 2 , N + 1 ): for j in range ( 2 , P): zero[i][j] = zero[i - 1 ][j - 1 ]; for j in range ( 1 , Q): zero[i][ 1 ] = (zero[i][ 1 ] + one[i - 1 ][j]); for j in range ( 2 , Q): one[i][j] = one[i - 1 ][j - 1 ]; for j in range ( 1 , P): one[i][ 1 ] = one[i][ 1 ] + zero[i - 1 ][j]; # Stores count of binary # Strings that satisfy # the given condition res = 0 ; # Count binary Strings of # length N having less than # P consecutive 0s for i in range ( 1 , P): res = res + zero[N][i]; # Count binary Strings of # length N having less than # Q consecutive 1s for i in range ( 1 , Q): res = res + one[N][i]; return res; # Driver Code if __name__ = = '__main__' :N = 5 ; P = 2 ; Q = 3 ; print (cntBinStr(N, P, Q)); # This code is contributed by gauravrajput1

C#

//C# program to implement //the above approach using System; class GFG{ //Function to count binary Strings //that satisfy the given condition static int cntBinStr( int N, int P, int Q) {//zero[i, j] stores count //of binary Strings of length i //having j consecutive 0s int [, ]zero = new int [N + 1, P]; //one[i, j] stores count //of binary Strings of length i //having j consecutive 1s int [, ]one = new int [N + 1, Q]; //Base case zero[1, 1] = one[1, 1] = 1; //Fill all the values of zero[i, j] //and one[i, j] in bottom up manner for ( int i = 2; i < = N; i++) { for ( int j = 2; j < P; j++) { zero[i, j] = zero[i - 1, j - 1]; } for ( int j = 1; j < Q; j++) { zero[i, 1] = zero[i, 1] + one[i - 1, j]; } for ( int j = 2; j < Q; j++) { one[i, j] = one[i - 1, j - 1]; } for ( int j = 1; j < P; j++) { one[i, 1] = one[i, 1] + zero[i - 1, j]; } } //Stores count of binary Strings //that satisfy the given condition int res = 0; //Count binary Strings of //length N having less than //P consecutive 0s for ( int i = 1; i < P; i++) { res = res + zero[N, i]; } //Count binary Strings of //length N having less than //Q consecutive 1s for ( int i = 1; i < Q; i++) { res = res + one[N, i]; } return res; } //Driver Code public static void Main(String[] args) { int N = 5, P = 2, Q = 3; Console.Write(cntBinStr(N, P, Q)); } } //This code is contributed by gauravrajput1

输出如下

7

时间复杂度：O(N *(P + Q))
辅助空间：O(N *(P + Q))

推荐阅读

• 

  索尼a7m3转接尼康镜头2470 索尼a7riii转接尼康镜头
• 

  在纸上写作
• 

  breathe和breath区别 breathe和breath有什么区别
• 

  一年当中电商节都有哪些 什么时候电商节，电商折扣每年哪些日子
• 

  酒驾行政复议需要多长时间
• 

  做快递赚钱吗？
• 

  唧唧复唧唧木兰当户织的意思 唧唧复唧唧木兰当户织的含义
• 

  势函数怎么求
• 

  普通铅笔涂卡能扫描吗 普通铅笔涂卡能不能扫描
• 

  看点|科技冬奥展看点多
• 

  大富翁网页版,7388大富翁网页版
• 

  喜欢一个不喜欢我的男生,怎么办？
• 

  为高一新生心理问题把脉 高一新生的心理调节
• 

  罗汉果的正确使用方法有哪些 教你正确使用罗汉果泡水
• 

  为什么俄罗斯敢跟美国叫板？
• 

  姜枣红糖茶的做法
• 

  违章代码13500是什么意思
• 

  完成率怎么算
• 

  女人长期喝枸杞菊花茶好吗
• 

  电视怎样连接wifi

• 给定操作生成的质因子求和序列的最大长度
• Salesforce面试经验|校园内
• 查找未排序数组中缺失的最小正数|S1
• Lex程序可计算行，空格和制表符的数量
• Win7可以不激活吗？Win7不激活会怎样样？
• spoon.sys损坏后，win7开机无法进入系统的处理办法
• win7系统关闭“交互式服务检测”提示窗口的办法
• win7定时开机的设置步骤
• 装win7开机出现checking media提示怎样办