อภิปรายปัญหาในการตอบคำถามไปยังอาร์เรย์ที่กำหนด สำหรับดัชนีการค้นหาแต่ละรายการ เราจำเป็นต้องค้นหาจำนวนหนึ่งและศูนย์ทางด้านซ้ายของดัชนี เป็นต้น
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 แนวทางในการหาแนวทางแก้ไข
แนวทางที่ไร้เดียงสา
วิธีแก้ปัญหาอย่างง่ายคือการสำรวจผ่านอาร์เรย์ไปยังดัชนีของแบบสอบถามและตรวจสอบแต่ละองค์ประกอบ หากเป็น 0 ให้เพิ่มตัวนับศูนย์อีก 1 ตัว ให้เพิ่มตัวนับทีละ 1
ตัวอย่าง
#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;
} ผลลัพธ์
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
แนวทางที่มีประสิทธิภาพ
ในแนวทางก่อนหน้านี้ ทุกครั้งที่เราคำนวณหนึ่งและศูนย์สำหรับการสืบค้นใหม่จากดัชนีที่ 0
อีกวิธีหนึ่งคือขั้นแรกในการคำนวณศูนย์และค่าที่อยู่ทางด้านซ้ายของทุกดัชนี เก็บไว้ในอาร์เรย์ และส่งคืนคำตอบตามดัชนีที่เขียนในแบบสอบถาม
ตัวอย่าง
#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;
} ผลลัพธ์
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
บทสรุป
ในบทช่วยสอนนี้ เราได้กล่าวถึงการคืนค่าจำนวนหนึ่งและศูนย์ทางด้านซ้ายของดัชนีสำหรับการค้นหาแต่ละรายการในอาร์เรย์ที่กำหนด เราได้พูดคุยถึงแนวทางง่ายๆ และแนวทางที่มีประสิทธิภาพในการแก้ปัญหานี้ เรายังพูดถึงโปรแกรม C++ สำหรับปัญหานี้ ซึ่งเราสามารถทำได้ด้วยภาษาโปรแกรม เช่น C, Java, Python เป็นต้น เราหวังว่าคุณจะพบว่าบทช่วยสอนนี้มีประโยชน์
