数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中包含 K 个 1 的二进制字符串子字符串计数
给定一个二进制数字字符串，即 0 和 1 的组合，以及一个整数 k，任务是计算由给定二进制字符串形成的、具有给定 k 个 1 的子字符串的数量。
输入 − 字符串 str = ‘10000100000’，k = 2
输出 − 包含 K 个 1 的二进制字符串的子字符串数为 − 6
解释 − 从给定字符串可以形成的子字符串有 1、10、100、1000、10000、010、100001、10001、1001、101、11、1000010。因此，有 6 个子字符串包含 k 个 1，即正好 2 个 1。
输入 − 字符串 str = ‘10000100000’，k = 3
输出 − 包含 K 个 1 的二进制字符串的子字符串数为 − 0
解释 − 我们给定一个整数 k 值为 3，如果我们检查包含二进制数字的字符串，它只有 2 个 1。因此，不可能存在具有给定 k 个 1 的子字符串。
下面程序中使用的方法如下
输入一个包含 0 和 1 组合的二进制数字字符串和一个整数变量 k。
使用 length() 函数计算字符串的长度，并将数据传递给函数以进行进一步处理。
声明一个临时变量 count 和 total 为 0，用于存储包含 k 个 1 的子字符串。
声明一个数组，用于存储大小为字符串长度加一的 1 的频率，并将其初始化为 0，并将数组的第一个元素设置为 1。
从 0 到数组长度开始循环 FOR
在循环内部，将 total 设置为 total + str[i] - ‘0’。检查 IF total >= k，然后将 count 设置为 count + arr[total-k]。
返回 count
打印结果。
示例
#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<<"Count of substrings of a binary string containing K ones are: "<<sub_k_ones(str, length, k) << endl;
return 0;
}输出
如果我们运行上述代码，它将生成以下输出：
Count of substrings of a binary string containing K ones are: 6
更新于: 2020-12-02
466 次浏览
广告