C++ 给定二进制字符串的所有K长度子字符串的位OR中置位的计数

置位是数字的二进制表示中的“1”位。数字的二进制表示仅包含两个数字“1”和“0”，也可以以字符串的形式存在。我们给出一个字符串，给定数的二进制表示和一个整数k。我们必须从给定的字符串中获取所有长度为k的子字符串，并对它们的位OR进行运算，最后，我们必须返回最终字符串中存在的置位的数量。

示例示例

输入

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)，因为我们使用嵌套的for循环来获取每个子字符串。

上述代码的空间复杂度为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的位OR操作。我们实现了两个程序，第一个是查找所有子字符串，然后对它们进行位OR操作。第二个方法是使用差异数组，并具有O(N)的空间和时间复杂度。