Chúng tôi được cung cấp một mảng arr [] chỉ chứa 0 và 1. Mục đích là đếm tất cả các mảng con của arr [] sao cho mỗi mảng con chỉ chứa 0 hoặc chỉ 1 chứ không phải cả hai. Nếu mảng là [1,0,0] .Subarrays sẽ chỉ dành cho 0 của [0], [0], [0,0] và chỉ cho 1 [1].
Hãy cho chúng tôi hiểu với các ví dụ.
Đầu vào - arr [] ={0, 0, 1, 1, 1, 0};
Đầu ra - Các mảng con chỉ có số 0 là:4 Nhóm con chỉ có số 1 là:6
Giải thích - Các nhóm phụ sẽ -
For all 0’s: [0], [0], [0], [0,0]. Total 4 ( arr[0], arr[1], arr[5], arr[0-1] ) For all 1’s: [1], [1], [1], [1,1], [1,1], [1,1,1]. Total 6 ( arr[2], arr[2], arr[4], arr[2-3], arr[3-4], arr[2-4] )
Đầu vào - arr [] ={1,0,1,0};
Đầu ra - Các mảng con chỉ có số 0 là:2 Nhóm con chỉ có số 1 là:2
Giải thích - Các nhóm phụ sẽ -
For all 0’s: [0], [0]. Total 2 ( arr[1], arr[3] ) For all 1’s: [1], [1]. Total 2 ( arr[0], arr[2] )
Cách tiếp cận được sử dụng trong chương trình dưới đây như sau
Chúng tôi sẽ duyệt qua mảng hai lần để đếm riêng biệt các mảng con chỉ có 0 và 1. Lấy hai bộ đếm count_0 và count_1 để lưu trữ số lượng các số 0 và 1 liên tiếp trong mảng. Đối với mỗi số lượng như vậy, các mảng con có thể có sẽ là count_0 * (count_0 + 1) / 2 và tương tự cho count_1.
Thêm điều này vào tổng_0 đếm cho đến khi đạt đến cuối mảng. Thực hiện quy trình tương tự cho 1’s.
-
Lấy một mảng [] số.
-
Hàm sub_zero_one (int arr [], int size) nhận mảng và trả về số lượng các mảng con chỉ có 0 và số lượng các mảng con chỉ có 1.
-
Lấy số lượng ban đầu là temp_0 và temp_1 cho các mảng con.
-
Lấy số đếm liên tiếp tạm thời của 0 và 1 làm đếm_0 và đếm_1.
-
Chúng ta sẽ duyệt qua mảng bằng vòng lặp for từ i =0 đến I
-
Nếu phần tử hiện tại là 0 số gia tăng_0.
-
Nếu không, hãy tính tất cả các mảng con có thể có với count_0 số 0 là temp_one_0 =count * (count + 1) / 2.
-
Thêm cái này vào temp_0 trước đó cho các mảng con với tất cả 0 được tìm thấy cho đến nay.
-
Thực hiện quy trình tương tự bằng cách sử dụng vòng lặp for cho 1 với các biến là count_1, temp_one_1 andtemp_1.
-
Khi kết thúc cả hai lần truyền, temp_0 và temp_1 sẽ có số lượng tương ứng của tất cả các mảng con trong arr có tất cả 0 và tất cả 1.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
void sub_zero_one(int arr[], int size){
int count_1 = 0;
int count_0 = 0;
int temp_1 = 0;
int temp_0 = 0;
for (int i = 0; i < size; i++){
if (arr[i] == 1){
count_1++;
}
else{
int temp_one_1 = (count_1) * (count_1 + 1) / 2;
temp_1 = temp_1 + temp_one_1;
count_1 = 0;
}
}
for (int i = 0; i < size; i++){
if (arr[i] == 0)
{ count_0++; }
else{
int temp_one_0 = (count_0) * (count_0 + 1) / 2;
temp_0 = temp_0 + temp_one_0;
count_0 = 0;
}
}
if (count_1){
int temp_one_1 = (count_1) * (count_1 + 1) / 2;
temp_1 = temp_1 + temp_one_1;
}
if (count_0){
int temp_one_0 = (count_0) * (count_0 + 1) / 2;
temp_0 = temp_0 + temp_one_0;
}
cout<<"Subarrays with only 0's are : "<<temp_0;
cout<<"\nSubarrays with only 1's are : "<<temp_1;
}
int main(){
int arr[] = { 0, 0, 0, 1, 1, 0, 1};
int size = sizeof(arr) / sizeof(arr[0]);
sub_zero_one(arr, size);
return 0;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Subarrays with only 0's are : 7 Subarrays with only 1's are : 4