C++中统计具有相同数量的1和0的子数组

给定一个仅包含0和1的数组arr[]。目标是统计arr[]的所有子数组，使得所有子数组中0和1的出现次数相等。如果数组是[1,0,0]。子数组将只有[1,0]。

让我们通过例子来理解。

输入 − arr[] = { 0, 0, 1, 1, 1, 0 };

输出 − 具有相同数量的1和0的子数组数量为- 4

说明 − 子数组将是-

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

说明 − 子数组将是- arr[0到1] = [0,1]

下面程序中使用的方案如下

我们将使用两个for循环遍历数组以生成所有可能的子数组。从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。

  • 我们将使用两个for循环从i=0到i<=size-1以及j=0到j<=size-1遍历数组。

  • 取两个变量total_0、total_1为0，分别表示子数组arr[i]到arr[j]中0和1的数量。

  • 将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);
}

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

输出

如果我们运行上述代码，它将生成以下输出：

Count of subarrays with equal number of 1’s and 0’s are: 4

更新于：2020年12月1日

425 次浏览

开启您的职业生涯

完成课程获得认证

开始学习
广告