資料結構
網路
關係資料庫管理系統 (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
