عد المصفوفات الفرعية بعدد متساوٍ من 1 و 0


مستوى الصعوبة سهل
كثيرا ما يطلب في سيسكو كوبون دنيا Coursera Databricks قيراط مختبرات SAP تسلا
مجموعة مزيج

المشكلة بيان

توضح مشكلة "عد المصفوفات الفرعية التي تحتوي على عدد متساوٍ من 1 و 0" أنه يتم منحك مصفوفة تتكون من 0 و 1 فقط. تطلب عبارة المشكلة معرفة عدد المصفوفات الفرعية التي تتكون من رقم صفر للإعلانات 0.

مثال

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

التفسير: جميع المصفوفات الفرعية هي (1,2،3,4) ، (0,3،1,4) ، (XNUMX،XNUMX) ، (XNUMX،XNUMX)

عد المصفوفات الفرعية بعدد متساوٍ من 1 و 0

 

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

شرح: جميع المصفوفات الفرعية هي (0، 1)، (2,3،0,3)، (1,4،0,5)، (4,5،2,5)، (XNUMX،XNUMX)، (XNUMX،XNUMX)، (XNUMX،XNUMX).

خوارزمية

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 فقط. سوف نستخدم تجزئة. سوف نعلن أ رسم خريطة. في الخريطة ، سنقوم بتخزين المجموع وتردده كـ 1. إذا كان جديدًا على الخريطة ، فقم بإضافته إلى الخريطة ، وإلا قم بزيادة تكرار قيمة المجموع السابق الموجودة في الخريطة.

ولكن قبل ذلك ، سنقوم بتحويل كل القيم من 0 إلى -1 ، أثناء عبور الحلقة ، إذا وجدنا عنصر مصفوفة كـ 0 ، فسنحوله إلى -1. إضافة قيمة عنصر المصفوفة الحالية إلى المجموع. سوف نتحقق من المجموع ، إذا كان المجموع يساوي 0 ، فسنقوم بزيادة قيمة المخرجات. هذا لأننا نقوم بتحويل جميع 0 إلى -1 ولدينا فقط 1 و 0. لذلك عندما نحول 0 إلى -1 ونضيف هذه القيمة بـ 1s. عندما يكون المجموع 0 ، يكون هذا ممكنًا فقط عندما يكون لدينا مساوٍ للأصفار والآحاد.

لنفترض أن لدينا ثلاثة آحاد وثلاثة أصفار ، وبتحويل كل صفر إلى -1 وجمع الثلاثة 0 وثلاثة -0 ، سيكون لدينا 1 كمجموع. هذا يعني أيضًا أنه بعد تحويل 1 إلى -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

تحليل التعقيد

الوقت C0 التعقيد

O (ن) أين "ن" هو عدد العناصر في المصفوفة. نظرًا لأننا استخدمنا HashMap ، فإننا قادرون على تحقيق تعقيد زمني خطي.

تعقيد الفضاء

O (ن) أين "ن" هو عدد العناصر في المصفوفة. هنا في HashMap ، قمنا بحفظ المجموع كمفتاح ، وبالتالي يتم تحقيق تعقيد الفضاء الخطي.