数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学给定二进制字符串的所有长度为 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;
// creating a function to get the required count
int getCount(string str, int k){
int len = str.size();
// defining the vector of size k. it will store the number of set bits at any place. Initially there will be zero at each bit
vector<int>bits(k,0);
// traversing over the string
for(int i=0; i<= len-k; i++){
// getting each substring
for(int j =0; j<k;j++){
if(str[i+j] == '1'){
// if current substring bit is set bit marking it in the vector
bits[j] = 1;
}
}
}
// traversing over the created vector to find the result
int ans = 0;
for(int i=0; i<k; i++){
if(bits[i] == 1){
ans++;
}
}
return ans; // returning the final answer
}
int main(){
string str = "1100111"; // given string
int k = 4; // given number
cout<<"The count of setbits in the bitwise OR of the given strings substrings of a given length is: "<<getCount(str,k)<<endl;
}
输出
The count of setbits in the bitwise OR of the given strings substrings of a given length is: 4
时间和空间复杂度
上述代码的时间复杂度为 O(N*N)，因为我们使用了嵌套循环来获取每个子串。
上述代码的空间复杂度为 O(N)，因为我们使用了一个数组来存储每个位置的位。
使用差分数组方法
在这种方法中，我们将使用差分数组方法来获取所需答案。首先，我们将创建一个函数来遍历字符串，并在函数中，我们将创建一个数组来存储差分数组结果。
我们将遍历字符串，对于每个索引，我们将获取数据，即当前索引可以在子串中达到哪个最大位置和最小位置，并将该信息标记在差分数组中。
我们将从开头遍历差分数组，并维护一个计数器，统计到目前为止发生的正数的次数。如果当前计数大于零，则将其计为集合位，最后我们将返回数组中集合位的总数。
示例
#include <bits/stdc++.h>
using namespace std;
// creating a function to get the required count
int getCount(string str, int k){
int len = str.size();
// defining the vector of size k. it will store the starting and ending of number that will make impact. initially there will be zero at each index
vector<int>bits(k+1,0);
// traversing over the string
for(int i=0; i < len; i++){
if(str[i] == '0'){
continue; // this bit will not make any impact
}
// getting starting and ending impact of the current index bit
int start;
start = max(0,k+i-len);
int end;
end = min(i,k-1);
// updating value int the difference array
bits[start]++;
bits[end+1]--;
}
// traversing over the created vector to find the result
int ans = 0;
int tot = 0;
for(int i=0; i<k; i++){
tot += bits[i];
if(tot > 0){
ans++;
}
}
return ans; // returning the final answer
}
int main(){
string str = "0110"; // given string
int k = 4; // given number
cout<<"The count of set bits in the bitwise OR of the given strings substrings of a given length is: "<<getCount(str,k)<<endl;
}
输出
The count of set bits in the bitwise OR of the given strings substrings of a given length is: 2
时间和空间复杂度
上述代码的时间复杂度为 O(N)，因为我们只遍历了字符串一次。此外，我们只遍历了相同大小的数组一次。
上述代码的空间复杂度为 O(N)，因为我们使用了一个数组来存储差分数组结果。
结论
在本教程中，我们实现了一个程序，用于查找给定字符串长度为 k 的子串的按位或运算结果中集合位的数量。我们实现了两个程序，第一个程序是查找所有子串，然后对它们进行按位或运算。第二种方法是使用差分数组，其时间和空间复杂度为 O(N)。
浏览量：106
