សំណួរជួរជួរដោយគ្មានការធ្វើបច្ចុប្បន្នភាព


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ BlackRock ក្រុមហ៊ុន GE សុខភាព មន្ទីរពិសោធន៍ Moonfrog Synopsys តាក់ស៊ី ៤ សុន Twilio
អារេ ឡាសាននិងធូបូ បញ្ហាសំណួរ

សេចក្តីថ្លែងការណ៍បញ្ហា។

បញ្ហា“ សំណួរជួរបូកដោយគ្មានការធ្វើបច្ចុប្បន្នភាព” បញ្ជាក់ថាអ្នកមាន អារេ of ចំនួនគត់ និងជួរមួយ។ សេចក្តីថ្លែងការណ៍បញ្ហាស្នើឱ្យរកផលបូកនៃធាតុទាំងអស់នៅក្នុងជួរដែលបានផ្តល់ឱ្យ។

ឧទាហរណ៍

arr[]={10, 9, 8, 7, 6}

Query: {(0, 4), (1, 3)}
40 24

ការពន្យល់

ផលបូកនៃលេខទាំងអស់រវាងជួរ (០, ៤) បញ្ចូលគ្នាគឺ ៤០ ហើយផលបូកនៃលេខទាំងអស់រវាងជួរ (១, ៣) រាប់បញ្ចូលគឺ ២៤ ។

សំណួរជួរជួរដោយគ្មានការធ្វើបច្ចុប្បន្នភាព

 

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

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

ការពន្យល់

យើងបានផ្តល់ជួរនៃចំនួនគត់និងជួរមួយយើងត្រូវបានស្នើឱ្យរកផលបូកនៃធាតុទាំងអស់នៅក្នុងជួរដែលបានផ្តល់សម្រាប់សំណួរនីមួយៗ។ សំណួរនីមួយៗមានជួរដែលជាចំណុចចាប់ផ្តើមនិងបញ្ចប់នៃជួរ។ សំណួរនេះមិនទាក់ទងនឹងសំណួរបច្ចុប្បន្នភាពទេ។ នោះមានន័យថាមិនចាំបាច់ធ្វើបច្ចុប្បន្នភាពអ្វីទេនៅពេលរកឃើញចម្លើយសំណួរ។ យើងគ្រាន់តែនឹងបង្កើតអារេដែលបានផ្តល់ឱ្យដូច្នេះផលបូកនៃធាតុទាំងអស់ពី ០ ដល់សន្ទស្សន៍បច្ចុប្បន្នគឺស្ថិតនៅទីតាំង ith នៃអារេដែលបានសាងសង់។ ដោយវិធីនេះរាល់សំណួរទាំងអស់នឹងត្រូវបានដោះស្រាយនៅក្នុងអូ (0) ដោយមានកន្លែងបន្ថែម O (n) ។

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

នៅពេលដែលយើងនឹងទទួលបានសំណួរដែលមានជួរណាមួយហើយប្រសិនបើយើងរកឃើញផ្នែកខាងឆ្វេងឬចំនុចចាប់ផ្តើមនៃជួរស្មើនឹង ០ យើងនឹងត្រឡប់មកវិញនូវតំលៃនៃ sumArray [ខាងស្ដាំ] ដែលជាអ្វីដែលយើងបានពិភាក្សាខាងលើគឺជួរខាងឆ្វេងគឺ មិនស្មើ ០ យើងនឹងត្រឡប់ភាពខុសគ្នានៃផលបូកអារេនៅខាងស្តាំនិងផលបូកអារេនៅខាងឆ្វេង។ ទាំងនេះនឹងជាចម្លើយដែលត្រូវការ។ វិធីសាស្រ្តនេះក៏ជាវិធីមួយដែលងាយស្រួលបំផុតក្នុងការប្រើប្រាស់ ការសរសេរកម្មវិធីឌីណាមិក.

លេខកូដ

កូដ C ++ សម្រាប់សំណួរបូកជួរដោយគ្មានការធ្វើបច្ចុប្បន្នភាព

#include<iostream>

using namespace std;

void buildSumArray(int arr[], int n, int sumArray[])
{
    sumArray[0] = arr[0];
    for (int i = 1; i < n; i++)
        sumArray[i] = arr[i] + sumArray[i - 1];
}

int solveQuery(int left, int right, int sumArray[])
{
    if (left == 0)
        return sumArray[right];

    return sumArray[right] - sumArray[left -1];
}

int main()
{
    int arr[] = {10,9,8,7,6};
    int n = sizeof(arr)/sizeof(arr[0]);

    int sumArray[n];

    buildSumArray(arr, n, sumArray);

    cout << solveQuery(0, 4, sumArray) << endl;
    cout << solveQuery(1, 3, sumArray) << endl;

    return 0;
}
40
24

កូដចាវ៉ាសំរាប់សំណួរជួរ Range ដោយគ្មានការធ្វើបច្ចុប្បន្នភាព

class RangeQueriesSum
{
    public static void buildSumArray(int arr[], int n, int sumArray[])
    {
        sumArray[0] = arr[0];
        for (int i = 1; i < n; i++)
            sumArray[i] = arr[i] + sumArray[i - 1];
    }

    public static int solveQuery(int left, int right, int sumArray[])
    {
        if (left == 0)
            return sumArray[right];

        return sumArray[right] - sumArray[left -1];
    }

    public static void main(String[] args)
    {
        int arr[] = {10,9,8,7,6};
        int n = arr.length;

        int sumArray[] = new int[n];

        buildSumArray(arr, n, sumArray);
        System.out.println(solveQuery(0, 4, sumArray));
        System.out.println(solveQuery(1, 3, sumArray));
    }
}
40
24

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

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

O (N + Q),  ពីព្រោះយើងត្រូវការ O (N) ដើម្បីគណនា sumArray ហើយបន្ទាប់មក O (1) ពេលវេលាសម្រាប់សំណួរនីមួយៗ។

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

នៅទីនេះនៅក្នុងវិធីសាស្រ្តដែលបានផ្តល់ឱ្យយើងបានបង្កើតអារេអារេថ្មីដើម្បីរក្សាទុកផលបូកនៃធាតុពី ០ ដល់អ៊ី។ ដូច្នេះវិធីសាស្រ្តនេះតម្រូវឱ្យមាន O (N) ចន្លោះ។ ប៉ុន្តែយើងក៏អាចកែប្រែអារេដើមបានដែរ។ បនា្ទាប់មកភាពស្មុគស្មាញអវកាសនឹងត្រូវបានកាត់បន្ថយទៅជាថេរ។