በተመሳሳዩ እኩል እና ያልተለመዱ ንጥረ ነገሮች ንዑስ ቤራጮችን ይ Countጥሩ


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ Accenture ፋርስት አፍቃሪዎች
ሰልፍ ሃሽ

ኢንቲጀር ሰጥተሃል እንበል ደርድር የ N መጠን። ቁጥሮች እንዳሉ ቁጥሮች ያልተለመዱ ወይም እንዲያውም ናቸው ፡፡ የችግሩ መግለጫ ተመሳሳይ እና ጎዶሎ አባላትን የያዘ የቁጥር ንዑስ ንዑስ ቡድን ነው ወይም እኩል እና ያልተለመዱ ቁጥሮች እኩል የሆኑ ንዑስ-ድርሰቶች ብዛት ያገኘዋል።

ለምሳሌ

ግቤት

arr [] = {2, 5, 1, 6};

ዉጤት

3

ማስረጃ

እንደ ⇒ {2, 5} ፣ {1, 6} ፣ {2, 5, 1, 6}

ግቤት

arr [] = {2,3,4,5,1,6}

ዉጤት

7

አልጎሪዝም

  1. የመጠን n + 1 መጠን ሁለት ድርድር ፣ አዎንታዊ ቁጥር እና አሉታዊ ቁጥር ያውጅ ፡፡
  2. ቆጠራ እና ውፅዓት ወደ 0 ያዘጋጁ ፣ እና አዎንታዊ ቁጥርን [0] ወደ 1 ያቀናብሩ።
  3. ድርድርን ያቋርጡ ከ i = 0 ፣ ወደ እኔ
    1. ቢትዊዝ እና ኦፕሬሽን arr [i] & 1 ከ 1 ጋር እኩል መሆኑን ያረጋግጡ
      1. እውነት ከሆነ ከዚያ ቆጠራውን በ 1 ይጨምሩ።
    2. ሌላ ፣ ቆጠራውን በ 1 ቀንሱ ፡፡
    3. ቆጠራው ከ 0 በታች ከሆነ ውጤቱን ወደ አሉታዊ ቁጥር [-count] ያክሉ እና ለውጤቱ ያከማቹ።
    4. ሌላ ፣ ውጤቱን ወደ positiveNum [count] ያክሉ እና ወደ ውፅዓት ያከማቹ።
  4. ተመላሽ ውጤት

ማስረጃ

ሁለቱን የሃሽ ድርድር እናደርጋለን ፣ አንዱ አዎንታዊውን ልዩነት ለማከማቸት ፣ አንዱ ደግሞ ለአሉታዊ ልዩነቶች ፡፡ ከልዩነቶች ጋር ፣ ያልተለመዱ እና አልፎ ተርፎም በብዛቶች መካከል ያለውን ልዩነት እናገኛለን ለማለት ነው ማለታችን ነው ፡፡ ውጤቱን ወደ 0 በማቀናበር ፣ በዚህ ውስጥ መልሳችንን እናሻሽላለን ፣ እስከ 0 ድረስ እንቆጥራለን ፣ ይህ የልዩነት ቆጠራውን ያቆየዋል ፡፡ ሁለት የሃሽ ድርድሮች ከታወጁ በኋላ ቀናውን ወደ 1 ፣ አዎንታዊ ቁጥር [0] = 1 ን ያቀናብሩ።

አደረጃጀቱን እናቋርጣለን ፣ እና ያልተለመደ እሴት ወይም አዎንታዊ መሆኑን እናረጋግጣለን ፣ ለዚህ ​​እኛ Bitwise እና ኦፕሬተርን እንጠቀማለን ፣ እና በ 1 እና በማንኛውም እሴት መካከል ያለውን ቢኤን እና ኦፕሬተርን የምንጠቀም ከሆነ ፣ ሁለቱን ውጤት 1 ወይም 0 እናገኛለን ፣ የ ቁጥር ጎዶሎ ነው እሱ እንደ ውፅዓት 1 ይሰጣል ፣ ያኔ ቢሆን እንኳን 0 እንደ ውፅዓት ይሰጣል። ቁጥሩ 1 ሆኖ ከተገኘ ከዚያ ቆጠራውን በ 1 እንጨምርበታለን ፣ ከዚያ 0 ብቻ ይችላል ፣ ስለሆነም ተመሳሳይ የቁጥር እሴት በ 1 እንቀንሳለን።

ይህንን እያደረግን ፣ ምርታችንን ጠብቀን መቆየት አለብን ፣ ምክንያቱም የቁጥር ዋጋ ከ 0 በታች ሆኖ ካገኘን ከዚያ የ ‹NNN› ቆጠራን የመረጃ ጠቋሚ እሴት ወደ ምርቱ እንጨምራለን እናም የ ‹NutN› ቁጥርን በ 1. እንጨምራለን ፡፡ ያገኘነው ቁጥሩን ከ 0 ይበልጣል ወይም እኩል ነው ፣ ስለሆነም የ ‹አዎንታዊ› ቁጥር መረጃ ጠቋሚ እሴቶችን በውጤቱ ላይ እየደመርን የ ‹አዎንታዊ› ቁጥርን በ 1. ከፍ እናደርጋለን አስፈላጊው ነገር የሁለቱም ተመሳሳይ እሴት ባገኘን ቁጥር ነው ፡፡ ሃሽ ድርድሮች የአሁኑ መረጃ ጠቋሚ ፣ ለእኛ እኩል ያልሆነ ንዑስ ድርድር አገኘን ማለት ነው ፡፡ እና በመጨረሻ ውጤቱን እንመልሳለን ፡፡

አፈጻጸም

ከተመሳሳይ እኩል እና ያልተለመዱ ንጥረ ነገሮች ጋር ለመቁጠር ንዑስ ሱራይዎች የ C ++ ፕሮግራም

#include<iostream>
#include<unordered_map>

using namespace std;

int getOESubarrays(int arr[], int n)
{
    int count = 0;
    int output = 0;

    int positiveNum[n+1];
    int negativeNum[n+1];

    positiveNum[0] = 1;

    for (int i = 0; i < n; i++)
    {
        if ((arr[i] & 1) == 1) count++;
        else count--;

        if (count < 0)
        {
            output += negativeNum[-count];
            negativeNum[-count]++;
        }
        else
        {
            output += positiveNum[count];
            positiveNum[count]++;
        }
    }
    return output;
}
int main()
{
    int arr[] = {2,3,4,5,1,6};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Even Odd Sub-Arrays are: " << getOESubarrays(arr,n);
    return 0;
}
Even Odd Sub-Arrays are: 7

የጃቫ ፕሮግራም በተመሳሳይ እና በተመሳሳይ ጎዶሎ ንጥረ ነገሮች ለቁጥር ንዑስ ቤቶች

class oddEvenSubArrays
{
    public static int getOESubarrays(int[] arr, int n)
    {
        int count = 0;
        int output = 0;

        int positiveNum[] = new int[n + 1];
        int negativeNum[] = new int[n + 1];

        positiveNum[0] = 1;

        for (int i = 0; i < n; i++)
        {
            if ((arr[i] & 1) == 1) count++;
            else count--;

            if (count < 0)
            {
                output += negativeNum[-count];
                negativeNum[-count]++;
            }
            else
            {
                output += positiveNum[count];
                positiveNum[count]++;
            }
        }
        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = {2,3,4,5,1,6};
        int n = arr.length;
        System.out.println("Even Odd Sub-Arrays are: "+getOESubarrays(arr, n));
    }
}
Even Odd Sub-Arrays are: 7

ከተመሳሳይ እኩል እና ያልተለመዱ ንጥረ ነገሮች ጋር ለመቁጠር ንዑስ ቤቶች ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ሆይ (n) የት “N” በድርድሩ ውስጥ ያሉት ንጥረ ነገሮች ብዛት ነው።

የቦታ ውስብስብነት

ኦ (2n) የት “N” በድርድሩ ውስጥ ያሉት ንጥረ ነገሮች ብዛት ነው።