დაითვალეთ ქვეჯგუფები იგივე ლუწი და კენტი ელემენტებით


Რთული ტური Easy
ხშირად ეკითხებიან Accenture ფაქტები ფანატიკა
Array Hash

დავუშვათ, რომ მთელი რიცხვი მიანიჭეთ მასივი 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, ხოლო დადებითიNum [0] დააყენეთ 1-ზე.
  3. მასივის გადაკვეთა i = 0 – დან i– მდე
    1. შეამოწმეთ, არის თუ არა ბიტისი და ოპერაციის ar [i] & 1 ტოლი 1,
      1. თუ სიმართლეა, მაშინ რიცხვი გაზრდით 1-ით.
    2. სხვაგან, შეამცირე რიცხვი 1-ით.
    3. თუ რაოდენობა 0-ზე ნაკლებია, შემდეგ დაამატეთ გამოსავალი negativeNum [-count] და შეინახეთ გამომავალზე.
    4. სხვაგვარად, დაამატეთ გამოცემა positiveNum- ში [რაოდენობა] და შეინახეთ გამოსაყვანად.
  4. დაბრუნების შედეგი.

განმარტება

ჩვენ გავაკეთებთ ორ ჰეშის მასივს, ერთი პოზიტიური სხვაობის შესანახად და ერთი უარყოფითი განსხვავებებისთვის. განსხვავებებით, ჩვენ ვგულისხმობთ იმის თქმას, რომ ჩვენ გავარკვევთ განსხვავებებს უცნაურ და ლუწ რიცხვთა სიხშირეებს შორის. გამოყვანის 0-ზე დაყენება, ჩვენ განვაახლებთ ჩვენს პასუხს, ჩავთვლით 0-მდე, ეს შეინარჩუნებს სხვაობის რაოდენობას. ორი ჰეშის მასივის გამოცხადების შემდეგ დადეთ პოზიტიური 1-ზე, positiveNum [0] = 1.

ჩვენ გადავხედავთ მასივს და შეამოწმებთ არის თუ არა ეს უცნაური მნიშვნელობა ან პოზიტიური, ამისათვის გამოვიყენებთ ოპერატორს Bitwise 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

ჯავა პროგრამა გრაფი ქვე-სვეტებისთვის იგივე ლუწი და კენტი ელემენტებით

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

სირთულის ანალიზი გრაფი სუბსტრატებისთვის იგივე ლუწი და კენტი ელემენტებით

დროის სირთულე

O (n) სადაც "ნ" არის მასივის ელემენტების რაოდენობა.

სივრცის სირთულე

O (2n) სადაც "ნ" არის მასივის ელემენტების რაოდენობა.