ในปัญหานี้ เราได้รับ N ช่วง [L, R] และ Q แบบสอบถามแต่ละรายการมี val ตัวเลข งานของเราคือการสร้างโปรแกรมเพื่อแก้ปัญหาแบบสอบถามเพื่อตรวจสอบว่าจำนวนอยู่ในช่วง N ของ L-R ใน C ++ หรือไม่
คำอธิบายปัญหา
เราได้รับ N ช่วงประเภท [L, R] ที่มีค่าจำนวนเต็มตั้งแต่ L ถึง R เช่น ช่วง [3, 6] มี 3,4,5,6 ในแต่ละแบบสอบถาม เราได้รับ val ซึ่งจะต้องตรวจสอบการมีอยู่ โปรแกรมจะคืนค่า จริง หาก val มีอยู่ในช่วงใดช่วงหนึ่ง มิฉะนั้น จะคืนค่าเท็จ
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล :ranges[N] ={{2, 4}, {6,7}, {9, 12}}
Q =3
ข้อความค้นหา ={1, 7, 10}
ผลผลิต :ไม่อยู่
นำเสนอ
นำเสนอ
คำอธิบาย
สำหรับคำถามที่ 1:ไม่มีหมายเลข 1 ในช่วงใด ๆ
สำหรับข้อความค้นหา 2:หมายเลข 7 อยู่ในช่วง {6, 7}
สำหรับข้อความค้นหา 1:ตัวเลข 10 อยู่ในช่วง {9, 12}
แนวทางการแก้ปัญหา
เราจำเป็นต้องตรวจสอบว่า val นั้นมีอยู่ในช่วงใดๆ หรือไม่ ดังนั้นเราต้องตรวจสอบ val ที่สอดคล้องกับทุกช่วง สำหรับสิ่งนี้ เราจะใช้ hashmap การจัดเก็บ L และ R ของช่วงแยกจากกัน จากนั้นการค้นหาโดยใช้อัลกอริทึมการค้นหาแบบไบนารีจะทำให้การแก้ปัญหาง่ายขึ้น
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
vector<int> v;
unordered_map<int, int> mpp;
void initialiseMap(int a[][2], int n){
for (int i = 0; i < n; i++) {
v.push_back(a[i][0]);
mpp[a[i][0]] = 1;
v.push_back(a[i][1]);
mpp[a[i][1]] = 2;
}
sort(v.begin(), v.end());
}
bool isElementPresent(int val) {
int ind = lower_bound(v.begin(), v.end(), val) - v.begin();
if (v[ind] == val)
return true;
else {
if (mpp[v[ind]] == 2)
return true;
else
return false;
}
}
int main(){
int arr[][2] = {{2, 4}, {6,7}, {9, 12}};
int n = 3;
int Q = 3;
int query[] = { 1, 7, 10 };
initialiseMap(arr, n);
for(int i = 0; i < Q; i++){
cout<<"For Query "<<(i+1);
if(isElementPresent(query[i]))
cout<<": The given digit "<<query[i]<<" is present in one of the given ranges\n";
else
cout<<": The given digit "<<query[i]<<" is not present in any of the given ranges\n";
}
return 0;
} ผลลัพธ์
For Query 1: The given digit 1 is not present in any of the given ranges For Query 2: The given digit 7 is present in one of the given ranges For Query 3: The given digit 10 is present in one of the given ranges
