សំណួរសម្រាប់តម្លៃទសភាគនៃ Subarrays នៃអារេគោលពីរ


កម្រិតលំបាក មធ្យម
សួរញឹកញាប់ ក្រុមហ៊ុន Amazon ក្រុមហ៊ុន google
អារេ បញ្ហាសំណួរ

សរសេរសំណួរសម្រាប់តម្លៃគោលដប់ subarrays នៃអារេគោលពីរក្នុងអារេគោលពីរដែលបានផ្តល់។ សេចក្តីថ្លែងការណ៍បញ្ហាស្នើឱ្យរកលេខទសភាគដែលបានបង្កើតឡើងដោយមានជំនួយពីជួរនៅក្នុងអារេគោលពីរ។

ឧទាហរណ៍

បញ្ចូល:

មកដល់ [] = {១០, ១២, ១៣, ១១, ៨, ១០, ១១, ១០}

សំណួរ (១, ៥)

សំណួរ (១, ៥)

លទ្ធផល:

12 9

ការពន្យល់:

លទ្ធផលដែលបានបង្កើតឡើងជាលេខគោលពីរដែលតំណាងឱ្យចន្លោះពី 1 ដល់ 5 បញ្ចូលគ្នា (01100) គឺ 12 ។

លទ្ធផលបានបង្កើតឡើងជាឯកសារ លេខគោលពីរ តំណាងឱ្យជួរពី ៣ ទៅ ៦ បញ្ចូលគ្នា (១០០១) គឺ ៩ ។

សំណួរសម្រាប់តម្លៃគោលដប់នៃអនុរ៉ាដានៃអារេគោលពីរ

 

ក្បួនដោះស្រាយសម្រាប់សំណួរសម្រាប់តម្លៃគោលដប់នៃអនុរ៉ាដានៃអារេគោលពីរ

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

ការពន្យល់សម្រាប់សំណួរសម្រាប់តម្លៃគោលដប់នៃអនុរ៉ាដានៃអារេគោលពីរ

ទាក់ទងនឹងបញ្ហាសំណួរសម្រាប់តម្លៃគោលដប់នៃអនុរ៉ាដានៃអារេគោលពីរដែលបានផ្តល់ឱ្យ អារេគោលពីរ និងជួរនៃសន្ទស្សន៍ដែលជាសន្ទស្សន៍ខាងឆ្វេងនិងសន្ទស្សន៍ខាងស្តាំ។ រកទំរង់គោលដប់នៃលេខគោលពីរដែលបានផ្តល់ឱ្យដូច្នេះបានបង្កើតឡើងជាមួយជួរដែលបានផ្តល់។ យើងនឹងត្រូវបានផ្តល់សំណួរដែលយើងបានផ្តល់ជួរ។ យើងត្រូវរកលេខទសភាគដូច្នេះបង្កើតជាចំនួនគោលពីរដែលមានលេខ។ ចំពោះបញ្ហានេះយើងនឹងបង្កើតអារេបន្ថែមនៃទំហំដូចគ្នានឹងប្រវែងអារេ។ យើងនឹងសាងសង់អារេនោះឬយើងអាចនិយាយបានថាយើងអាចរៀបចំជាមុននូវអារេនោះហើយបំពេញនូវតម្លៃមួយចំនួននៅក្នុងវាដូច្នេះយើងអាចដោះស្រាយសំណួរនៅក្នុងពេលវេលាថេរ។

ឆ្លងកាត់អារេប៉ុន្តែមុនពេលឆ្លងកាត់អារេបំពេញអារេដោយ 0 ។ នៅក្នុងជ្វានៅពេលដែលអារេត្រូវបានបង្កើតវាត្រូវបានបំពេញដោយស្វ័យប្រវត្តិដោយលេខ 0 ប៉ុន្តែនៅក្នុង C ++ យើងត្រូវធ្វើវាដោយខ្លួនឯង។ បន្ទាប់ពីនោះទទួលបានផលិតផលនៃធាតុអារេចុងក្រោយនិង 1 រក្សាទុកតម្លៃនៅក្នុងធាតុចុងក្រោយនៃបុព្វបទអារេ។ ឥឡូវចាប់ផ្តើមពីស្តាំទៅឆ្វេងមានន័យថាចាប់ផ្តើមពីលេខ ២nd ធាតុចុងក្រោយនៃអារេឥឡូវទទួលបានផលគុណនៃលេខដែលមាននៅក្នុងស្វ័យគុណ ២ និងធាតុអារេដែលបានផ្តល់ហើយបន្ថែមវាជាមួយតំលៃមុននៃបុព្វបទអារេ។ បន្តបន្ថែមវាជាមួយតម្លៃនៃបុព្វបទអារេហើយរក្សាទុកវាទៅកន្លែងរៀងៗខ្លួននៃបុព្វបទអារេ។

ចំពោះសំណួរនីមួយៗដែលបានផ្តល់ឱ្យយើងពិនិត្យមើលថាតើតម្លៃត្រឹមត្រូវដែលបានផ្តល់មិនស្មើនឹងសន្ទស្សន៍ចុងក្រោយនៃអារេ។ ប្រសិនបើវាត្រូវបានរកឃើញថាពិតបន្ទាប់មកយកបុព្វបទខុសគ្នា [ឆ្វេង] និងបុព្វបទអារេរ៉េខាងស្តាំហើយចែកវាជាមួយតំលៃដែលបានបង្កើតឡើងនៅពេលយើងអនុវត្តប្រតិបត្តិការវេននៅក្នុងអានុភាពនៃលេខ ២ ហើយត្រឡប់តម្លៃនោះបើមិនដូច្នោះទេគ្រាន់តែត្រឡប់ភាពខុសគ្នា នៃបុព្វបទអារេរ៉ា [ខាងឆ្វេង] និងចែកវាជាមួយប្រតិបត្តិការវេននៅលើតម្លៃត្រឹមត្រូវហើយប្រគល់វាមកវិញ។

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

កម្មវិធី C ++

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string.h>

using namespace std;

void buildArray(int arr[], int n, int prefixArray[])
{
    memset(prefixArray, 0, n * sizeof(int));
    prefixArray[n - 1] = arr[n - 1] * pow(2, 0);
    for (int i = n - 2; i >= 0; i--)
        prefixArray[i] = prefixArray[i + 1] + arr[i] * (1 << (n - 1 - i));
}
int getDeimalNum(int arr[], int left, int right, int n, int prefixArray[])
{
    if (right!= n - 1)
        return (prefixArray[left] - prefixArray[right + 1]) / (1 << (n - 1 - right));

    return prefixArray[left] / (1 << (n - 1 - right));
}
int main()
{
    int arr[] = {1, 0, 1, 1, 0, 0, 1, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);

    int prefixArray[n];
    buildArray(arr, n, prefixArray);
    cout << getDeimalNum(arr, 1, 5, n, prefixArray) << endl;
    cout << getDeimalNum(arr, 3, 6, n, prefixArray) << endl;
    return 0;
}
12
9

កម្មវិធីចាវ៉ា

import java.util.Arrays;

class DecimalfromSubArray
{
    static void buildArray(int arr[], int n, int prefixArray[])
    {
        Arrays.fill(prefixArray, 0);
        prefixArray[n - 1] = arr[n - 1] * (int)(Math.pow(2, 0));
        for (int i = n - 2; i >= 0; i--)
        {
            prefixArray[i] = prefixArray[i + 1] + arr[i] * (1 << (n - 1 - i));
        }
    }
    
    static int getDeimalNum(int arr[], int left, int right, int n, int prefixArray[])
    {
        if (right != n - 1)
        {
            return (prefixArray[left] - prefixArray[right + 1]) / (1 << (n - 1 - right));
        }
        return prefixArray[left] / (1 << (n - 1 - right));
    }
    
    public static void main(String[] args)
    {
        int arr[] = {1, 0, 1, 1, 0, 0, 1, 1};
        int n = arr.length;

        int prefixArray[] = new int[n];
        buildArray(arr, n, prefixArray);

        System.out.println(getDeimalNum(arr,1, 5, n, prefixArray));

        System.out.println(getDeimalNum(arr,3, 6, n, prefixArray));
    }
}
12
9

ការវិភាគស្មុគស្មាញសម្រាប់សំណួរសម្រាប់តម្លៃទសភាគនៃ Subarrays នៃអារេគោលពីរ

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

O (q) ដែលជាកន្លែងដែល "Q" គឺជាចំនួនសំណួរ។

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

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

ឯកសារយោង