ในบทความนี้ เราจะให้คำอธิบายสั้น ๆ เกี่ยวกับการแก้จำนวนอาร์เรย์ย่อยที่มีระดับบิต OR>=K ใน C++ ดังนั้นเราจึงมีอาร์เรย์ 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++ -
กำลังดุร้าย
ในแนวทางนี้ เราจะผ่านอาร์เรย์ย่อยทั้งหมดที่สามารถเกิดขึ้นได้ และตรวจสอบว่า OR มากกว่าหรือเท่ากับ 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 ซึ่งก็คือมันไม่เคยลดลงเลยแม้ว่าเราจะเพิ่มตัวเลขเข้าไปอีก ดังนั้นหากเราได้รับอาร์เรย์ย่อยจาก i ถึง j ที่มีค่า OR มากกว่าหรือเท่ากับ K ดังนั้นทุกๆ อาร์เรย์ย่อยที่มีช่วง {i,j} จะมี OR มากกว่า 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)) ซึ่งเป็นสิ่งที่ดีมาก ตอนนี้ โปรแกรมนี้ยังสามารถใช้ได้กับข้อจำกัดที่ใหญ่กว่า ไม่เหมือนก่อนหน้านี้
บทสรุป
ในบทความนี้ เราแก้ปัญหาเพื่อค้นหาจำนวนอาร์เรย์ย่อยที่มี OR>=K ในความซับซ้อนของเวลา O(nlog(n)) โดยใช้ Binary Search and Segment Tree . นอกจากนี้เรายังได้เรียนรู้โปรแกรม C ++ สำหรับปัญหานี้และแนวทางที่สมบูรณ์ ( Normal และ มีประสิทธิภาพ ) โดยที่เราแก้ไขปัญหานี้ เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, java, python และภาษาอื่นๆ หวังว่าบทความนี้จะเป็นประโยชน์
