给定二进制字符串的所有 K 长度子字符串的按位或中的设置位计数
设置位是数字的二进制表示中为"1"的位。数字的二进制表示仅包含两位"1"和"0"，也可能以字符串的形式存在。我们给定一个字符串、给定数字的二进制表示和一个整数 k。我们必须从给定的字符串中获取长度为 k 的所有子字符串，并对它们进行按位或，最后，我们必须返回最终字符串中存在的设置位数。
示例
输入
string str = "1100111" int k = 4
输出
4
说明:我们有四个子字符串:1100、1001、0011 和 0111，每个子字符串的按位或结果为 1111，这意味着这里有四个设置位。
输入
string str = 0110 int k = 4
输出
2
说明:我们只有一个子字符串，即给定的字符串，因此设置位数为 2。
获取所有子字符串
在这种方法中，我们将遍历字符串并通过遍历字符串的总长度减去子字符串的大小来获取所有子字符串。
我们将通过获取单个子字符串当前索引的值来存储最终子字符串每个索引处存在的位，即如果它是 1，则通过按位或最终为 1。
示例
#include <bits/stdc++.h>
using namespace std;
// 创建一个函数来获取所需的计数
int getCount(string str, int k){
int len = str.size();
// 定义大小为 k 的向量。它将在任意位置存储设置位数。最初每个位为零
vector<int>bits(k,0);
// 遍历字符串
for(int i=0; i<= len-k; i++){
// 获取每个子字符串
for(int j =0; j<k;j++){
if(str[i+j] == '1'){
// 如果当前子字符串位被设置，则在向量中标记它
bits[j] = 1;
}
}
}
// 遍历创建的向量来查找结果
int ans = 0;
for(int i=0; i<k; i++){
if(bits[i] == 1){
ans++;
}
}
return ans; // 返回最终答案
}
int main(){
string str = "1100111"; // 给定字符串
int k = 4; // 给定数字
cout<<"给定字符串子字符串的按位或中 setbits 的数量为: "<<getCount(str,k)<<endl;
}
输出
给定字符串子字符串的按位或中 setbits 的数量为: 4
时间和空间复杂度
上述代码的时间复杂度为 O(N*N)，因为我们使用嵌套 for 循环来获取每个子字符串。
上述代码的空间复杂度为 O(N)，因为我们使用数组来存储每个位置预设的位。
使用差异数组方法
在此方法中，我们将使用差异数组方法来获取所需的答案。首先，我们将创建一个函数来遍历字符串，并在该函数中创建一个数组来存储差异数组结果。
我们将遍历字符串，对于每个索引，我们将获取当前索引在子字符串中可以达到的最大位置和最小位置的数据，并将其标记在差异数组中。
我们将从头开始遍历差异数组，并保持到目前为止发生的正向拦截次数的计数。如果当前计数大于零，则我们将其计为设置位，最后我们将返回数组中存在的设置位总数。
示例
#include <bits/stdc++.h>
using namespace std;
// 创建一个函数来获取所需的计数
int getCount(string str, int k){
int len = str.size();
// 定义大小为 k 的向量。它将存储会产生影响的数字的开始和结束。最初每个索引处都会有零
vector<int>bits(k+1,0);
// 遍历字符串
for(int i=0; i < len; i++){
if(str[i] == '0'){
continue; // 此位不会产生任何影响
}
// 获取当前索引位的起始和结束影响
int start;
start = max(0,k+i-len);
int end;
end = min(i,k-1);
// 更新差异数组中的值
bits[start]++;
bits[end+1]--;
}
// 遍历创建的向量来查找结果
int ans = 0;
int tot = 0;
for(int i=0; i<k; i++){
tot += bits[i];
if(tot > 0){
ans++;
}
}
return ans; // 返回最终答案
}
int main(){
string str = "0110"; // 给定字符串
int k = 4; // 给定数字
cout<<"给定长度的给定字符串子字符串的按位或中设置位数的计数为:"<<getCount(str,k)<<endl;
}
输出
给定长度的给定字符串子字符串的按位或中设置位数的计数为:2
时间和空间复杂度
上述代码的时间复杂度为 O(N)，因为我们只遍历字符串一次。此外，我们只遍历了相同大小的数组一次。
上述代码的空间复杂度为 O(N)，因为我们使用数组来存储差异数组结果。
结论
在本教程中，我们实现了一个程序来查找字符串中存在的设置位数，该字符串是子字符串的按位或或给定字符串的长度 k。我们实现了两个程序，第一个是查找所有子字符串，然后对所有子字符串进行按位或。第二种方法是使用差异数组，其空间和时间复杂度为 O(N)。
