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

  • Z时代
  • 2024-01-10
  • 分类：综合

我们得到一串二进制数，即 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'。检查 IF total >= k 然后将 count 设置为 count + arr[total-k]。

  • 返回计数

  • 打印结果。

示例

#include <bits/stdc++.h>
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 个的二进制串的子串数为： "<<sub_k_ones(str, length, k) << endl;
   return 0;
}
输出结果

如果我们运行上面的代码，它将生成以下输出 -

包含 K 个的二进制串的子串数为： 6

以上是 C++中包含K个的二进制字符串的子字符串计数 的全部内容， 来源链接： utcz.com/z/359717.html

回到顶部