Հաշվիր ենթագրերը նույն նույն և կենտ տարրերով


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են 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, իսկ positiveNum [0] - ը դարձրեք 1:
  3. Անցեք զանգվածը i = 0-ից մինչև i
    1. Ստուգեք արդյոք բիթային և գործողության ar [i] & 1 հավասար է 1-ին,
      1. Եթե ​​ճիշտ է, ապա ավելացրեք հաշվարկը 1-ով:
    2. Ուրիշը, հաշիվը 1-ով իջեցրու:
    3. Եթե ​​հաշվարկը 0-ից պակաս է, ապա արդյունքը ավելացրե՛ք negativeNum- ին [-հաշվին] և պահեք այն ելքի համար:
    4. Այլապես, արդյունքը ավելացրու positiveNum- ին [հաշվարկի] և պահիր այն ելքի համար:
  4. Վերադարձի արդյունքը:

բացատրություն

Մենք կկազմենք երկու հեշ զանգված, մեկը դրական տարբերությունը պահելու համար, և մեկը բացասական տարբերությունների համար: Տարբերություններով, մենք ուզում ենք ասել, որ մենք պարզելու ենք տարօրինակ և հավասար ամբողջ թվերի հաճախությունների միջև տարբերությունները: Արդյունքը դնելով 0, դրանում մենք կթարմացնենք մեր պատասխանը, կհաշվենք 0, սա կպահպանի տարբերության քանակը: Երկու հեշ զանգվածներ հայտարարելուց հետո դրականը դրեք 1-ի վրա, positiveNum [0] = 1:

Մենք կկողմնորոշենք զանգվածը և ստուգենք, թե դա տարօրինակ արժեք է, թե՞ դրական, դրա համար մենք կօգտագործենք Bitwise AND օպերատոր, եթե օգտագործենք AND օպերատորը 1-ի և ցանկացած արժեքի միջև, մենք կստանանք երկու արդյունքը ՝ 1 կամ 0, եթե որ թիվը տարօրինակ է դա կտա 1-ը որպես ելք, եթե նույնիսկ այն ժամանակ է, ապա այն տալիս է 0-ը որպես ելք: Եթե ​​հայտնաբերված թիվը 1 է, ապա մենք պատրաստվում ենք հաշվելը մեծացնել 1-ով, այլապես դա կարող է լինել միայն 0, այնպես որ նույն հաշվարկի արժեքը 1-ով կիջեցնենք:

Դա անելիս մենք պետք է պահպանենք մեր արտադրանքը, քանի որ եթե մենք գտնում ենք, որ հաշվարկի արժեքը 0-ից փոքր է, ապա մենք արդյունքի վրա կավելացնենք բացասական Թվաքանակի ինդեքսի արժեքի արժեքը և բացասական Թվի Քանակը կավելացնենք 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

Java ծրագիր `նույն զույգ և կենտ տարրերով հաշվարկի ենթաշերտերի համար

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

Բարդության վերլուծություն նույն հավասար և կենտ տարրերով հաշվարկի ենթաշերտերի համար

Timeամանակի բարդություն

O (n) որտեղ «Ն» զանգվածում տարրերի քանակն է:

Տիեզերական բարդություն

Օ (2 ն) որտեղ «Ն» զանգվածում տարրերի քանակն է: