ចំនួនសន្ទស្សន៍ដែលមានធាតុស្មើគ្នានៅក្នុងជួរដែលបានផ្តល់


កម្រិតលំបាក មធ្យម
សួរញឹកញាប់ ប្រផេះក្រូច ជា​ការ​ពិត ល្ខោនអូប៉េរ៉ា Pinterest Snapdeal ក្រុមហ៊ុន Yahoo
អារេ បញ្ហាសំណួរ

អ្នកត្រូវបានផ្តល់ឱ្យ integer អារេ, សំណួរ Q និងជួរមួយនៅខាងឆ្វេងនិងស្តាំ។ “ ចំនួនលិបិក្រមដែលមានធាតុស្មើគ្នាក្នុងជួរដែលបានផ្តល់ឱ្យ” និយាយថាដើម្បីរកចំនួនសរុបនៃចំនួនគត់ក្នុងវិធីមួយដែលបន្សល់ <= i <ខាងស្តាំដូចជា Ai = កj + 1.

ឧទាហរណ៍

arr[] = {2, 2, 3, 3, 3, 4, 4, 4, 4}
Query = 2
Left = 2, right = 6
Left = 4, right = 8
3
3

ការពន្យល់

សម្រាប់សំណួរទី ១ កន្លែងដែលនៅសល់ = ២, ស្ដាំ = ៦

arr[2]=arr[3], arr[3]=arr[4], arr[5]=arr[6]

ការរាប់គឺ ៣ ។

សម្រាប់សំណួរទី ២ កន្លែងដែលនៅសល់ = ៤, ស្ដាំ = ៨

arr[5]=arr[6], arr[6]=arr[7], arr[7]=arr[8]

ការរាប់គឺ ៣ ។

ចំនួនសន្ទស្សន៍ដែលមានធាតុស្មើគ្នានៅក្នុងជួរដែលបានផ្តល់

 

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

  1. បង្កើតអារេមួយ។
  2. ឆ្លងកាត់អារេ។
  3. ប្រសិនបើធាតុអារេបច្ចុប្បន្នស្មើនឹងធាតុបន្ទាប់បន្ទាប់មកសម្គាល់ធាតុរបស់អារេដែលបានបង្កើតគឺស្មើនឹង ១ ។
  4. ប្រសិនបើលិបិក្រមមិនស្មើនឹង ០ បន្ទាប់មកទុកផលបូកនៃធាតុអារេបច្ចុប្បន្នរបស់អាដមមីនិងធាតុអារេបន្ទាប់ចូលទៅក្នុងអារេដាមមីម [i] ។
  5. ដោះស្រាយសំណួរប្រសិនបើទីតាំងខាងឆ្វេងស្មើ ០ ហើយបន្ទាប់មកត្រឡប់អារេឌមមីម [ស្តាំ -១១] ផ្សេងទៀតត្រឡប់ភាពខុសគ្នានៃអារេដាមម៉ាំង [ស្តាំ -១] និងអារេដាមមីម [ឆ្វេង -១] ។

ការពន្យល់

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

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

ចំពោះសំណួរនីមួយៗដែលបានផ្តល់ប្រសិនបើសន្ទស្សន៍ខាងឆ្វេងនៃជួរស្មើនឹង ០ បន្ទាប់មកត្រឡប់ជួរអារេឌមមីម [ស្តាំ - ១] ។ ក្រៅពីនេះប្រសិនបើវាមិនមែនជាលេខ ០ ទេនោះសូមត្រឡប់ភាពខុសគ្នារវាងអាដ្រាមម៉ាំង (ស្ដាំ - ១) និងអារេដាមម៉ាំង [ឆ្វេង - ១]

លេខកូដ

កូដ C ++ ដើម្បីរាប់ចំនួនលិបិក្រមដែលមានធាតុស្មើគ្នាក្នុងជួរដែលបានផ្តល់

#include <iostream>

using namespace std;

int arrayDummy[100];

void getNumbers(int a[], int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        if (a[i] == a[i + que
            arrayDummy[i] = 1;

        if (i != 0)
            arrayDummy[i] += arrayDummy[i - 1];
    }
}

int solveQuery(int l, int r)
{
    if (l == 0)
        return arrayDummy[r - 1];
    else
        return arrayDummy[r - 1] - arrayDummy[l - 1];
}

int main()
{
    int arr[] = { 2,2,3,3,3,4,4,4,4};
    int n = sizeof(arr) / sizeof(arr[0]);

    getNumbers(arr, n);

    int left, right;

    left = 2;
    right = 6;

    cout << solveQuery(left, right) << endl;
    left = 4;
    right = 8;
    cout << solveQuery(left, right) << endl;
    return 0;
}
3
3

លេខកូដចាវ៉ាដើម្បីរាប់ចំនួនលិបិក្រមដែលមានធាតុស្មើគ្នាក្នុងជួរដែលបានផ្តល់

class IndexElementsEqual
{
    static int arrayDummy[] = new int[1000];

    public static void getNumbers(int arr[], int n)
    {
        for (int i = 0; i < n-1; i++)
        {
            if (arr[i] == arr[i + 1])
                arrayDummy[i] = 1;

            if (i != 0)
                arrayDummy[i] += arrayDummy[i - 1];
        }
    }
    public static int solveQuery(int left, int right)
    {
        if (left == 0)
            return arrayDummy[right - 1];
        else
            return arrayDummy[right - 1] - arrayDummy[left - 1];
    }
    public static void main(String args[])
    {
        int arr[] = {2,2,3,3,3,4,4,4,4};
        int n = arr.length;

        getNumbers(arr, n);

        int left, right;

        left = 2;
        right = 6;

        System.out.println(solveQuery(left, right));
        left = 4;
        right = 8;
        System.out.println(solveQuery(left, right));
    }
}
3
3

ការវិភាគស្មុគស្មាញ

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

 ឱ (១) សម្រាប់រាល់សំណួរនិង អូរ (n) សម្រាប់ការគណនាមុន។

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

អូរ (n) ដែលជាកន្លែងដែល “ n” គឺជាចំនួនធាតុក្នុងអារេ។ ចន្លោះនេះត្រូវបានទាមទារសម្រាប់ការបង្កើតអារេដមមី។