រាប់ Subarrays ជាមួយធាតុដូចគ្នានិងសេស


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ Accenture រោងចក្រ និយមជ្រុល
អារេ ហាស់

ឧបមាថាអ្នកបានផ្តល់លេខគត់ អារេ នៃទំហំ N ។ ដូចជាមានលេខដែរលេខគឺសេសឬគូ។ សេចក្តីថ្លែងអំពីបញ្ហាគឺការរាប់បញ្ចូលគ្នាជាមួយធាតុដូចគ្នានិងសេសឬរកឃើញចំនួនអនុជួរដែលមានចំនួនស្មើរនៃចំនួនគត់គូនិងសេស។

ឧទាហរណ៍

បញ្ចូល

មកដល់ [] = {២, ៥, ១, ៦};

ទិន្នផល

3

ការពន្យល់

ដូចមាន⇒ {២, ៥}, {១, ៦}, {២, ៥, ១, ៦}

បញ្ចូល

មកដល់ [] = {2,3,4,5,1,6}

ទិន្នផល

7

ក្បួនដោះស្រាយ

  1. ប្រកាសអារេចំនួនពីរវិជ្ជមាននិងគុណវិបត្តិអវិជ្ជមាននៃទំហំ n + 1 ។
  2. កំណត់ចំនួននិងលទ្ធផលទៅ ០ ហើយកំណត់លេខវិជ្ជមានពី ០ ដល់ ១ ។
  3. ឆ្លងកាត់អារេ ពី i = 0, ទៅខ្ញុំ
    1. ពិនិត្យមើលថាតើការប្រតិបត្ដិការបន្តិចនិងប្រតិបត្ដិការមកដល់ [i] & ១ ស្មើនឹង ១,
      1. បើពិតបន្ទាប់មកបង្កើនចំនួន ១ ។
    2. ផ្សេងទៀតបន្ថយការរាប់ដោយ 1 ។
    3. ប្រសិនបើការរាប់តិចជាង ០, បន្ទាប់មកបន្ថែមលទ្ធផលទៅលេខអវិជ្ជមាន - ហើយបញ្ចូលវាទៅលទ្ធផល។
    4. ម៉្យាងទៀតបន្ថែមលទ្ធផលទៅជាវិជ្ជមាន - រាប់ហើយទុកវាឱ្យលទ្ធផល។
  4. ត្រឡប់លទ្ធផល។

ការពន្យល់

យើងនឹងធ្វើអារេទាំងពីរគឺមួយសំរាប់ផ្ទុកភាពវិជ្ជមានហើយមួយទៀតគឺសំរាប់ភាពខុសគ្នាអវិជ្ជមាន។ ជាមួយនឹងភាពខុសគ្នាយើងចង់និយាយថាយើងនឹងរកឃើញភាពខុសគ្នារវាងប្រេកង់នៃលេខសេសនិងលេខគត់។ កំណត់លទ្ធផលទៅ ០ ក្នុងនេះយើងនឹងធ្វើបច្ចុប្បន្នភាពចម្លើយរបស់យើងរាប់ទៅ ០ វានឹងរក្សាចំនួនខុសគ្នា។ បន្ទាប់ពីបានប្រកាសអារេពីរដាក់កំណត់វិជ្ជមានមួយដល់លេខ ១ វិជ្ជមានលេខ ០ [=] = ១ ។

យើងនឹងឆ្លងកាត់អារេហើយពិនិត្យមើលថាតើវាជាតម្លៃសេសឬវិជ្ជមានសម្រាប់វាយើងនឹងប្រើប្រតិបត្តិករប៊ីតខលនិងប្រតិបត្តិករប្រសិនបើប្រើសញ្ញាប្រមាណវិធី AND រវាង ១ និងតម្លៃណាមួយយើងនឹងទទួលបានលទ្ធផលទាំងពីរគឺ ១ ឬ ០ ប្រសិនបើ នេះ លេខគឺសេស វានឹងផ្តល់ ១ ជាលទ្ធផលប្រសិនបើវានៅពេលនោះវាផ្តល់ ០ ជាលទ្ធផល។ ប្រសិនបើលេខបានរកឃើញថាមានលេខ ១ នោះយើងនឹងបង្កើនការរាប់ដោយ ១ បើមិនដូច្នេះទេវាអាចត្រឹមតែ ០ ទេដូច្នេះយើងនឹងបន្ថយតម្លៃរាប់ដដែលដោយ ១

ខណៈពេលដែលយើងធ្វើដូចនេះយើងគួរតែរក្សាលទ្ធផលរបស់យើងព្រោះប្រសិនបើយើងរកឃើញថាចំនួននៃការរាប់គឺតិចជាង ០ នោះយើងនឹងបន្ថែមគុណតំលៃនៃសន្ទស្សន៍នៃការរាប់អវិជ្ជមានទៅនឹងលទ្ធផលនិងបង្កើនចំនួនអវិជ្ជមានដោយ ១ ។ យើងរកឃើញតែលេខធំជាងឬស្មើ ០ ដូច្នេះយើងនឹងបន្ថែមគុណតំលៃនៃសន្ទស្សន៍វិជ្ជមានរបស់អិនអិនចំពោះលទ្ធផលនិងបង្កើនចំនួននៃគុណវិជ្ជមានដោយ ១ ។ រឿងសំខាន់គឺពេលណាដែលយើងរកតំលៃដូចគ្នានៃទាំងពីរ សញ្ញានេះបង្ហាញពីសន្ទស្សន៍បច្ចុប្បន្នវាមានន័យថាយើងបានរកឃើញអនុជួរសេសសម្រាប់យើង។ ហើយនៅចុងបញ្ចប់យើងនឹងត្រលប់មកវិញនូវលទ្ធផល។

ការអនុវត្តន៍

កម្មវិធី C ++ សំរាប់ Count Subarrays ជាមួយធាតុដដែលនិងសេស

#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

កម្មវិធីចាវ៉ាសំរាប់ Count Subarrays ជាមួយធាតុដដែលនិងធាតុសេស

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

ការវិភាគស្មុគស្មាញសម្រាប់ចំនួន Subarrays ដែលមានធាតុដូចគ្នានិងសេស

ស្មុគស្មាញពេលវេលា

អូរ (n) ដែលជាកន្លែងដែល “ n” គឺជាចំនួនធាតុក្នុងអារេ។

ភាពស្មុគស្មាញនៃលំហ

O (2n) ដែលជាកន្លែងដែល “ n” គឺជាចំនួនធាតុក្នុងអារេ។