เราได้รับอาร์เรย์ arr[] ที่มี 0 และ 1 เท่านั้น เป้าหมายคือการนับอาร์เรย์ย่อยทั้งหมดของ arr[] เพื่อให้การเกิดขึ้นของ 0 และ 1 เท่ากันทั้งหมด หากอาร์เรย์เป็น [1,0,0] .Subarray จะเป็น [1,0] เท่านั้น
ให้เราเข้าใจด้วยตัวอย่าง
ป้อนข้อมูล − arr[] ={ 0, 0, 1, 1, 1, 0 };
ผลผลิต − จำนวนอาร์เรย์ย่อยที่มีจำนวนเท่ากับ 1 และ 0 คือ − 4
คำอธิบาย − Subaarays จะเป็น -
arr[0 to 3] = [0,0,1,1], arr[1 to 2] = [0,1], arr[4 to 5] =[1,0], Arr[0 to 5] =[0,0,1,1,1,0].
ป้อนข้อมูล − arr[] ={ 0, 1, 1, 1, 1 };
ผลผลิต − จำนวนอาร์เรย์ย่อยที่มีจำนวนเท่ากับ 1 และ 0 คือ − 1
คำอธิบาย − Subaarays จะเป็น − arr[0 ถึง 1] =[0,1]
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้
เราจะสำรวจอาร์เรย์โดยใช้สองลูปเพื่อสร้างอาร์เรย์ย่อยทั้งหมดที่เป็นไปได้ จาก i=0 ถึง i<=size-1 และ j=i ถึง j<=size-1 อาร์เรย์ย่อยที่ก่อตัวขึ้นจะอยู่ระหว่าง arr[i] ถึง arr[j] นับความถี่ 0 และ 1 ในแต่ละอาร์เรย์ย่อย หากเท่ากันให้เพิ่มจำนวนขึ้น
-
หาอาร์เรย์ arr[] ของตัวเลข
-
ฟังก์ชั่น sub_zeroes_ones(int arr[], int size) รับอาร์เรย์และส่งกลับจำนวนอาร์เรย์ย่อยที่มีค่าเท่ากับ จาก 0 และ 1
-
นับเริ่มต้นเป็น 0
-
เราจะสำรวจอาร์เรย์โดยใช้สองลูปจาก i=0 ถึง i<=size-1 และ j=0 ถึง j<=size-1
-
นำสองตัวแปร total_0, total_1 เป็น 0 สำหรับจำนวน 0 และ 1 ใน subarray arr[i] ถึง arr[j]
-
เปรียบเทียบ arr[j] กับ 0 และ 1 หาก arr[j] เป็น 0 หรือ 1 ให้เพิ่มจำนวนตามลำดับ ( total_0 หรือ total_1)
-
ถ้า total_0==total_1 นับเพิ่ม. (อาร์เรย์ย่อยมีจำนวน 0 และ 1 เท่ากันเป็นองค์ประกอบ)
-
ที่ส่วนท้ายของลูปทั้งสอง ให้นับกลับเป็นผลลัพธ์
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
int sub_zeroes_ones(int arr[], int size){
int count = 0;
for (int i = 0; i <= size - 1; i++){
int total_0 = 0;
int total_1 = 0;
for (int j = i; j <= size - 1; j++){
if (arr[j] == 0){
total_0++;
}
else if (arr[j] == 1){
total_1++;
}
if(total_0 == total_1){
count++;
}
}
}
return count;
}
int main(){
int arr[] = {0, 1, 1, 0, 0};
int size = sizeof(arr)/sizeof(arr[0]);
cout<<"Count of subarrays with equal number of 1’s and 0’s are: "<<sub_zeroes_ones(arr, size);
} ผลลัพธ์
หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -
Count of subarrays with equal number of 1’s and 0’s are: 4
