Пребройте подчините с еднакъв брой 1 и 0  


Ниво на трудност Лесно
Често задавани в Cisco CouponDunia Coursera Датчици за данни Карат SAP Labs Tesla
Array Хашиш

Декларация за проблема  

Проблемът „Преброяване на подмасиви с еднакъв брой 1 и 0“ гласи, че ви се дава масив, състоящ се само от 0 и 1. Изложението на проблема изисква да се открие броят на подмасивите, състоящи се от равно на 0 на рекламите 1.

Пример  

arr[] = {0, 0, 1, 1, 0}
4

Обяснение: Всички подредове са (1,2), (3,4), (0,3), (1,4)

Пребройте подчините с еднакъв брой 1 и 0

 

arr[] = {1,0,0,1,1,0}
7

Обяснение: Всички под-масиви са (0), (1), (2,3), (0,3), (1,4), (0,5), (4,5).

алгоритъм  

1. Declare the map.
2. Set the output and sum to 0.
3. Traverse the array, while i<n.
  1. Set arr[i] = -1, if arr[i] is equal to 0.
  2. Add the value of arr[i] to the sum.
  3. If the sum is equal to 0, then increase the value of output by 1.
  4. If the map contains the sum, then add the output to the frequency of the current sum’s value in the map.
  5. If the map contains the value sum, then just increase the frequency of the previous sum’s frequency in the map by 1.
  6. Else put that new sum and marks its frequency as 1.
4. Return output.

Обяснение

Дадохме масив, състоящ се само от 0 и 1. И така, трябва да открием броя на подмасивите, които съдържат само 0 и 1. Ще използваме хеширане. Ще обявим a карта. В карта ще съхраним сумата и нейната честота като 1. Ако тя е нова за картата, добавете я към картата, в противен случай увеличете честотата на стойността на предходната сума в картата.

Вижте също
Напишете код, за да определите дали две дървета са идентични

Но преди това ще преобразуваме всички 0 в -1, докато обхождаме цикъла. Ако намерим елемент на масив като 0, ще го преобразуваме в -1. Събиране на стойността на текущия елемент на масива към сумата. Ще проверим за сумата, ако сумата е равна на 0, ще увеличим стойността на изхода. Това е така, защото преобразуваме всички 0 в -1 и имаме само 1 и 0. Така че, когато преобразуваме 0 в -1 и добавяме тази стойност с 1s. Когато сумата е 0, това е възможно само когато имаме равни 0 и 1.

Да предположим, че имаме три 1 и три 0 и преобразувайки всяко 0 в -1 и събирайки трите 1 и три -1, ще имаме 0 като сума. Това също означава, че след преобразуване на 0 в -1, за да имаме 0 като сума, трябва да имаме равни 0 и 1. Така че, когато намерите стойността на сумата като 0, ние ще увеличим изходната стойност. Имайки предвид входния масив, ще актуализираме стойността на изхода, когато получим сумата като 0.

код  

C ++ код за преброяване на подмасиви с еднакъв брой 1 и 0

#include <iostream>
#include<map>

using namespace std;

int getSubArrayWithEqual01(int arr[], int n)
{
    map<int,int> MAP;
    int sum=0;
    int output=0;
    for (int i = 0; i < n; i++)
    {
        if (arr[i] == 0)
            arr[i] = -1;

        sum += arr[i];

        if (sum == 0)
            output++;

        if (MAP[sum])
            output += MAP[sum];

        if(MAP[sum]==0)
            MAP[sum]=1;
        else
            MAP[sum]++;
    }
    return output;
}
int main()
{
    int arr[] = { 0, 0, 1, 1, 0};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout<<"Sub-Arrays with equal 0's and 1's count is: " <<getSubArrayWithEqual01(arr, n);
}
Sub-Arrays with equal 0's and 1's count is: 4

Java код за преброяване на подмасиви с еднакъв брой 1 и 0

import java.util.HashMap;
class SubArrayCount01
{
    public static int getSubArrayWithEqual01(int[] arr, int n)
    {
        HashMap<Integer, Integer> MAP = new HashMap<>();
        int sum = 0;
        int output = 0;
        for (int i = 0; i < n; i++)
        {
            if (arr[i] == 0)
            {
                arr[i] = -1;
            }
            sum += arr[i];

            if (sum == 0)
            {
                output++;
            }
            if (MAP.containsKey(sum))
                output += MAP.get(sum);

            if (!MAP.containsKey(sum))
            {
                MAP.put(sum, 1);
            }
            else
            {
                MAP.put(sum, MAP.get(sum) + 1);
            }
        }
        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = { 0, 0, 1, 1, 0 };
        int n = arr.length;
        System.out.println("Sub-Arrays with equal 0's and 1's count is:" +getSubArrayWithEqual01(arr, n));
    }
}
Sub-Arrays with equal 0's and 1's count is:4

Анализ на сложността  

Време C0mplexity

О (п) където "н" е броят на елементите в масива. Тъй като използвахме HashMap, ние можем да постигнем линейна сложност във времето.

Вижте също
Дължина на най-големия подмасив със съседни елементи

Сложност на пространството

О (п) където "н" е броят на елементите в масива. Тук в HashMap сме запазили сумата като ключ, като по този начин се постига линейна сложност на пространството.