好资源导航 » 文章资讯 » C++中包含K个的二进制字符串的子字符串计数

C++中包含K个的二进制字符串的子字符串计数

2023-06-21 14:32:03 66

我们得到一串二进制数，即0和1以及整数值k的组合，任务是计算由给定k个1的给定二进制串形成的子串的计数。

输入-字符串str='10000100000',k=2

输出-包含K个的二进制字符串的子串计数为-6

说明-可以从给定的字符串形成的子串是1,10,100,1000,10000,010,100001,10001,1001,101,11,1000010.所以有6个子串的1的个数正好为2.

输入-字符串str='10000100000',k=3

输出-包含K个的二进制字符串的子串计数为-0

说明-我们给出了一个整数k作为3，如果我们检查包含二进制数的字符串，它只有2个。所以子串不可能给出k个1。

下面程序中使用的方法如下

输入一串由0和1组合而成的二进制数和一个整数变量k。

使用length()函数计算字符串的长度并将数据传递给函数进行进一步处理。

声明一个临时变量count和total为0，用于存储k个子串。

声明一个数组来存储大小为字符串长度加一的频率，并将其初始化为0并将数组的第一个元素设置为1。

从0开始循环FOR直到数组的长度

在循环内，将total设置为total+str[i]-'0'。检查IFtotal>=k然后将count设置为count+arr[total-k]。

返回计数

打印结果。

示例

#include 
using namespace std;
int sub_k_ones(string str, int length, int k){
   int count = 0;
   int total_1 = 0;
   int arr_fre[length + 1] = {0};
   arr_fre[0] = 1;
   for (int i = 0; i < length; i++){
      total_1 = total_1 + (str[i] - '0');
      if (total_1 >= k){
         count = count + arr_fre[total_1 - k];
      }
      arr_fre[total_1]++;
   }
   return count;
}
int main(){
   string str = "10000100000";
   int length = str.length();
   int k = 2;
   cout<<"包含K个的二进制串的子串数为： "<输出结果
如果我们运行上面的代码，它将生成以下输出-
包含K个的二进制串的子串数为： 6

返回顶部
514930285
czq8825@qq.com

C++中包含K个的二进制字符串的子字符串计数

下面程序中使用的方法如下

示例

热门推荐

随机推荐