Thảo luận về một vấn đề để trả lời các truy vấn cho mảng đã cho. Ví dụ:đối với mỗi chỉ mục truy vấn, chúng ta cần tìm số lượng chỉ mục và số không ở bên trái chỉ mục.
Input: arr[ ] = { 0, 1, 1, 1, 0, 0, 0, 1, 0, 0}, queries[ ] = { 2, 4, 1, 0, 5 }
Output:
query 1: zeros = 1,ones = 1
query 2: zeros = 1,ones = 3
query 3: zeros = 1,ones = 0
query 4: zeros = 0,ones = 0
query 5: zeros = 2,ones = 3
Input: arr[ ] = { 0, 0, 1, 1, 1, 0, 1, 0, 0, 1 }, queries[ ] = { 3, 2, 6 }
Output:
query 1: zeros = 2,ones = 1
query 2: zeros = 2,ones = 0
query 3: zeros = 3,ones = 3 Phương pháp tiếp cận để tìm giải pháp
Phương pháp tiếp cận ngây thơ
Giải pháp đơn giản cho vấn đề này là duyệt qua mảng đến chỉ mục của truy vấn và kiểm tra từng phần tử; nếu nó là 0, sau đó tăng bộ đếm 0 lên 1 khác, tăng bộ đếm một lên 1.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
int main(){
int nums[] = {1, 0, 0, 1, 1, 0, 0, 1, 0, 0};
int queries[] = { 2, 4, 1, 0, 5 };
int qsize = sizeof(queries) / sizeof(queries[0]);
int zeros=0,ones=0;
// loop for running each query.
for(int i = 0;i<qsize;i++){
//counting zeros and ones
for(int j = 0;j<queries[i];j++){
if(nums[j]==0)
zeros++;
else
ones++;
}
cout << "\nquery " << i+1 << ": zeros = " << zeros << ",ones = " << ones;
zeros=0;
ones=0;
}
return 0;
} Đầu ra
query 1: zeros = 1,ones = 1 query 2: zeros = 2,ones = 2 query 3: zeros = 0,ones = 1 query 4: zeros = 0,ones = 0 query 5: zeros = 2,ones = 3
Phương pháp tiếp cận hiệu quả
Trong cách tiếp cận trước đây, chúng tôi luôn tính toán các số một và số không cho các truy vấn mới từ chỉ mục thứ 0.
Một cách tiếp cận khác là trước tiên tính toán các số không và các số không có ở bên trái của mọi chỉ mục, lưu trữ chúng trong một mảng và trả về câu trả lời theo chỉ mục được viết trong truy vấn.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
int main(){
int nums[] = {1, 0, 0, 1, 1, 0, 0, 1, 0, 0};
int queries[] = { 2, 4, 1, 0, 5 };
int n = sizeof(nums) / sizeof(nums[0]);
int arr[n][2];
int zeros = 0, ones = 0;
// traverse through the nums array.
for (int i = 0; i < n; i++) {
// store the number of zeros and ones in arr.
arr[i][0] = zeros;
arr[i][1] = ones;
// increment variable according to condition
if (nums[i]==0)
zeros++;
else
ones++;
}
int qsize = sizeof(queries) / sizeof(queries[0]);
for (int i = 0; i < qsize; i++)
cout << "\nquery " << i+1 << ": zeros = " << arr[queries[i]][0] << ",ones =" << arr[queries[i]][1];
return 0;
} Đầu ra
query 1: zeros = 1,ones = 1 query 2: zeros = 2,ones = 2 query 3: zeros = 0,ones = 1 query 4: zeros = 0,ones = 0 query 5: zeros = 2,ones = 3
Kết luận
Trong hướng dẫn này, chúng tôi đã thảo luận về việc trả về số lượng đơn vị và số không ở bên trái chỉ mục cho mỗi truy vấn trong mảng đã cho. Chúng tôi đã thảo luận về một cách tiếp cận đơn giản và một cách tiếp cận hiệu quả để giải quyết vấn đề này. Chúng tôi cũng đã thảo luận về chương trình C ++ cho vấn đề này mà chúng tôi có thể làm với các ngôn ngữ lập trình như C, Java, Python, v.v. Chúng tôi hy vọng bạn thấy hướng dẫn này hữu ích.