資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究使用C++查詢按位或運算結果大於等於K的子陣列個數
在本文中，我們將簡要說明如何使用C++解決按位或運算結果大於等於K的子陣列個數的問題。我們有一個數組arr[]和一個整數K，我們需要找到按位或(OR)運算結果大於等於K的子陣列個數。以下是該問題的示例：
Input: arr[] = {1, 2, 3} K = 3
Output: 4
Bitwise OR of sub-arrays:
{1} = 1
{1, 2} = 3
{1, 2, 3} = 3
{2} = 2
{2, 3} = 3
{3} = 3
4 sub-arrays have bitwise OR ≥ 3
Input: arr[] = {3, 4, 5} K = 6
Output: 2解決方法
現在我們將使用兩種不同的方法來使用C++解決這個問題：
暴力法
在這種方法中，我們將遍歷所有可能的子陣列，並檢查其按位或運算結果是否大於等於K。如果是，則遞增答案。
示例
#include <bits/stdc++.h>
using namespace std;
int main(){
int arr[] = {1, 2, 3}; // given array.
int k = 3;
int size = sizeof(arr) / sizeof(int); // the size of our array.
int answer = 0; // the counter variable.
for(int i = 0; i < size; i++){
int bitwise = 0; // the variable that we compare to k.
for(int j = i; j < size; j++){ // all the subarrays starting from i.
bitwise = bitwise | arr[j];
if(bitwise >= k) // if bitwise >= k increment answer.
answer++;
}
}
cout << answer << "\n";
return 0;
}輸出
4
這種方法非常簡單，但它也有缺點，因為它對於較高的約束條件並不理想，因為對於較高的約束條件，它將花費太多時間，因為這種方法的時間複雜度為**O(N*N)**，其中N是給定陣列的大小，因此我們現在將採用一種更高效的方法。
高效方法
在這種方法中，我們將使用OR運算子的一些特性，即即使我們新增更多數字，它也不會減小，因此，如果我們得到一個按位或運算結果大於等於K的子陣列(從i到j)，則包含範圍{i,j}的每個子陣列的按位或運算結果都將大於K，我們將利用此特性來改進我們的程式碼。
示例
#include <bits/stdc++.h>
#define N 1000
using namespace std;
int t[4*N];
void build(int* a, int v, int start, int end){ // segment tree building
if(start == end){
t[v] = a[start];
return;
}
int mid = (start + end)/2;
build(a, 2 * v, start, mid);
build(a, 2 * v + 1, mid + 1, end);
t[v] = t[2 * v] | t[2 * v + 1];
}
int query(int v, int tl, int tr, int l, int r){ // for processing our queries or subarrays.
if (l > r)
return 0;
if(tl == l && tr == r)
return t[v];
int tm = (tl + tr)/2;
int q1 = query(2*v, tl, tm, l, min(tm, r));
int q2 = query((2*v)+1, tm+1, tr, max(tm+1, l), r);
return q1 | q2;
}
int main(){
int arr[] = {1, 2, 3}; // given array.
int k = 3;
int size = sizeof(arr) / sizeof(arr[0]); // the size of our array.
int answer = 0; // the counter variable.
build(arr, 1, 0, size - 1); // building segment tree.
for(int i = 0; i < size; i++){
int start = i, end = size-1;
int ind = INT_MAX;
while(start <= end){ // binary search
int mid = (start + end) / 2;
if(query(1, 0, size-1, i, mid) >= k){ // checking subarray.
ind = min(mid, ind);
end = mid - 1;
}
else
start = mid + 1;
}
if(ind != INT_MAX) // if ind is changed then increment the answer.
answer += size - ind;
}
cout << answer << "\n";
return 0;
}輸出
4
在這種方法中，我們使用二分查詢和線段樹，這有助於將我們的時間複雜度從**O(N*N)降低到O(Nlog(N))**，這非常好。現在，與前面一種方法不同，此程式也可以處理更大的約束條件。
結論
在本文中，我們使用**二分查詢和線段樹**解決了查詢按位或運算結果大於等於K的子陣列個數的問題，時間複雜度為O(nlog(n))。我們還學習了針對此問題的C++程式以及解決此問題的完整方法（常規方法和高效方法）。我們可以使用C、Java、Python和其他語言編寫相同的程式。希望本文對您有所幫助。
更新於：2021年11月24日
758 次瀏覽
廣告