计算可能的长度为N的二进制字符串，而没有P个连续的0和Q个连续的1

2021年5月1日17:20:44 发表评论 897 次浏览

本文概述

给定三个整数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

时间复杂度：

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))

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: