ከ 1 እና ከ 0 ዎቹ እኩል ቁጥር ያላቸው ንዑስ ቤራጮችን ይ Countጥሩ


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ Cisco ኩፖንዱኒያ Coursera የመረጃ ቋቶች Karat የ SAP ላብራቶሪዎች tesla
ሰልፍ ሃሽ

የችግሩ መግለጫ

ችግሩ “ከ 1 እና ከ 0 ጋር እኩል የሆኑ ንዑስ ቤራዎችን ይቆጥሩ” የሚለው 0 እና 1 ብቻ ያካተተ ድርድር ይሰጥዎታል ይላል ፡፡ የችግር መግለጫው ከ 0 ዎቹ ማስታወቂያ 1 ዎቹ ጋር እኩል ያልሆኑ ንዑስ-ድርደራዎች ብዛት ለማወቅ ይጠይቃል።

ለምሳሌ

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

ማብራሪያ-ሁሉም ንዑስ-ስብስቦች (1,2) ፣ (3,4) ፣ (0,3) ፣ (1,4)

ከ 1 እና ከ 0 ዎቹ እኩል ቁጥር ያላቸው ንዑስ ቤራጮችን ይ Countጥሩ

 

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

ማብራሪያ-ሁሉም ንዑስ-ድርድሮች (0 ፣ 1) ፣ (2,3) ፣ (0,3) ፣ (1,4) ፣ (0,5) ፣ (4,5) ፣ (2,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 ን ብቻ የያዙ ንዑስ-ድርሰቶች ቆጠራን መፈለግ አለብን ፡፡ ልንጠቀምበት ነው ሃምሽንግ. እኛ እናሳውቃለን ካርታ. በካርታ ውስጥ ድምርን እና ድግግሞሹን እንደ 1. እናከማቸዋለን XNUMX. ለካርታው አዲስ ከሆነ ከዚያም በካርታው ላይ ያክሉት ፣ ከዚያ በካርታው ውስጥ ያለው የቀደመው ድምር ዋጋ ድግግሞሽ ይጨምሩ ፡፡

ከዚያ በፊት ግን ሁሉንም 0 ቶች ወደ -1 እንለውጣቸዋለን ፣ በሉፉ ላይ ስናልፍ ፣ እንደ 0 ያለ የድርጅት አካል ካገኘን ወደ -1 እንቀይረዋለን ፡፡ የአሁኑን የድርድር ንጥረ ነገር ዋጋን ወደ ድምር ማከል። ድምርን እንፈትሻለን ፣ ድምር ከ 0 ጋር እኩል ከሆነ የውጤት ዋጋን ከፍ እናደርጋለን። ይህ የሆነበት ምክንያት ሁሉንም 0 ቶች ወደ -1 እየቀየርናቸው እና 1 እና 0 ብቻ ስላለን ነው ፡፡ ስለዚህ 0 ን ወደ -1 ስንቀይር እና ያንን እሴት ከ 1 ቶች ጋር ስናክል ፡፡ ድምርው 0 በሚሆንበት ጊዜ ሁሉ ይህ ሊሆን የሚችለው እኩል 0 እና 1 ሲኖረን ብቻ ነው ፡፡

ሶስት 1 እና ሶስት 0 ቢኖረን ፣ እና እያንዳንዱን 0 ወደ -1 በመቀየር እና ሦስቱን 1 እና ሶስት -1 በመደመር 0 እንደ ድምር ይኖረናል እንበል ፡፡ ይህ ደግሞ የሚያመለክተው 0 ን ወደ -1 ከቀየርን በኋላ 0 በድምሩ እንዲኖረን እኩል 0 እና 1. ሊኖረን ይገባል ማለት ነው ፡፡ ስለዚህ የደመወዝ ዋጋን እንደ 0 ባገኙ ቁጥር የውጤት ዋጋውን እንጨምራለን ፡፡ የግብዓት ድርድርን ከግምት በማስገባት ድምርን በ 0 ባገኘን ቁጥር የውጤት ዋጋን እናዘምነዋለን ፡፡

ኮድ

የ 1 እና 0 እኩል ቁጥር ያላቸውን ንዑስ ቤቶችን ለመቁጠር የ C ++ ኮድ

#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

የ ‹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

ሆይ (n) የት “N” በድርድሩ ውስጥ ያሉት ንጥረ ነገሮች ብዛት ነው። ሃሽማፕን ስለተጠቀምን የመስመር ጊዜ ውስብስብነትን ለማሳካት ችለናል ፡፡

የቦታ ውስብስብነት

ሆይ (n) የት “N” በድርድሩ ውስጥ ያሉት ንጥረ ነገሮች ብዛት ነው። እዚህ በሃሽ ማፕ ውስጥ ድምሩን እንደ ቁልፍ አስቀምጠናል ፣ ስለሆነም ቀጥተኛ የቦታ ውስብስብነት ተገኝቷል ፡፡