数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律学C++ 中统计二进制数组中仅包含 0 或仅包含 1 的子数组数量
给定一个数组 arr[]，其中只包含 0 和 1。目标是计算 arr[] 的所有子数组，使得每个子数组只包含 0 或只包含 1，而不是两者都包含。如果数组是 [1,0,0]。对于仅包含 0 的子数组将是 [0]，[0]，[0,0]，而对于仅包含 1 的子数组将是 [1]。
让我们通过示例来理解。
输入 − arr[] = { 0, 0, 1, 1, 1, 0 };
输出 − 仅包含 0 的子数组数量：4 仅包含 1 的子数组数量：6
解释 − 子数组将是 −
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] )
输入 − arr[] = { 1,0,1,0 };
输出 − 仅包含 0 的子数组数量：2 仅包含 1 的子数组数量：2
解释 − 子数组将是 −
For all 0’s: [0], [0]. Total 2 ( arr[1], arr[3] ) For all 1’s: [1], [1]. Total 2 ( arr[0], arr[2] )
下面程序中使用的算法如下
我们将遍历数组两次，分别统计仅包含 0 和仅包含 1 的子数组。使用两个计数器 count_0 和 count_1 来存储数组中连续 0 和 1 的数量。对于每个这样的计数，可能的子数组将是 count_0*(count_0+1)/2，对于 count_1 也是如此。
将此添加到 total_0 计数器中，直到到达数组的末尾。对 1 执行类似的过程。
取一个包含数字的数组 arr[]。
函数 sub_zero_one(int arr[], int size) 获取数组并返回仅包含 0 的子数组数量和仅包含 1 的子数组数量。
将初始计数作为 temp_0 和 temp_1 用于子数组。
将 0 和 1 的临时连续计数作为 count_0 和 count_1。
我们将使用 for 循环从 i=0 到 I <size 遍历数组。
如果当前元素为 0，则递增 count_0。
如果不是，则计算所有可能的子数组，这些子数组具有 count_0 个 0，作为 temp_one_0=count*(count+1)/2。
将其添加到以前的 temp_0 中，以获取到目前为止找到的所有包含 0 的子数组。
使用 for 循环对 1 执行类似的过程，变量为 count_1、temp_one_1 和 temp_1。
在两次遍历结束时，temp_0 和 temp_1 将分别包含 arr 中所有包含 0 和所有包含 1 的子数组的数量。
示例
#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;
}输出
如果我们运行以上代码，它将生成以下输出：
Subarrays with only 0's are : 7 Subarrays with only 1's are : 4
443 次浏览
