資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
