用C++编写一个程序来计算以'1'开头并以'1'结尾的子串的数量

2023-06-21 10:52:03 77

让我们假设我们已经给出了一个字符串'str'的长度和一个字符串。任务是计算给定二进制字符串中以“1”开头并以“1”结尾的子字符串的数量。二进制字符串仅包含“1”和“0”。例如，

输入1-

N = 5
str = ‘11101’

输出-

说明-在给定的二进制字符串中，我们有6个以“1”开头并以“1”结尾的子字符串。这些子串的集合是{'11','111','1110','11101','1101','101'}。

输入1-

N = 4
str = ‘0011’

输出-

说明-

在给定的二进制字符串中，我们有1个以“1”开头并以“1”结尾的子字符串。这些子串的集合是一个单例集合，即{'11'}。

用来解决这个问题的方法

对于给定的字符串，我们必须计算以“1”开头并以“1”结尾的子字符串的数量。这个问题类似于众所周知的握手问题，在这个问题中，我们必须计算一组“n”人的握手次数。

如果我们计算给定字符串中1的数量，那么我们可以找到以“1”开头并以“1”结尾的子字符串集。

输入一个长度为N的字符串。

Integer函数countSubstring(intN,strings)将字符串的长度和字符串作为输入，并返回以“1”开头并以“1”结尾的所有子字符串的计数。

遍历整个字符串并计算编号。字符串中的“1”。

数一数。给定字符串中的子字符串（对）的n*(n-1)/2。

返回n*(n-1)/2的结果。

示例

#include
using namespace std;
int countSubstring(int N, string s){
   int count=0;
   for(int i=0; s[i]!= '\0'; ++i){
      if( s[i]== '1' )
         count++;
   }
   return count*(count-1)/2;
}
int main() {
   int N=5;
   string str= "11101";
   cout<< countSubstring(N,str)<输出结果
如果我们运行上面的代码，那么它会打印输出，
6
由于给定字符串中存在的'1'个数为'4'，即count=4，因此以'1'开头并以'1'结尾的子字符串的总数为4*(4-1)/2=6。

用C++编写一个程序来计算以'1'开头并以'1'结尾的子串的数量

用来解决这个问题的方法

示例

热门推荐

随机推荐