Екілік массивтің кіші массивтерінің ондық мәндеріне арналған сұрақтар


Күрделілік дәрежесі орта
Жиі кіреді Amazon Google
Array Сұрақ мәселесі

Берілген екілік алапта екілік массивтің ішкі жиымдарының ондық мәндеріне сұраныстар жазыңыз. Есептер қойылымы екілік массивтегі диапазонның көмегімен құрылған ондық санды табуды сұрайды.

мысал

Кіру:

arr [] = {1, 0, 1, 1, 0, 0, 1, 1}

Сұрау (1, 5)

Сұрау (3, 6)

Шығару:

12 9

Түсіндіру:

1-ден 5-ке дейін (01100) дейінгі аралықты білдіретін екілік сандар ретінде қалыптасқан нәтиже 12 құрайды.

Шығарылым осылайша қалыптасты екілік сандар 3-тен 6-ға дейін (1001) қоса алғанда, 9 құрайды.

Екілік массивтің ішкі жиымдарының ондық мәндеріне сұраныстар

 

Екілік массивтің ішкі жиымдарының ондық мәндеріне арналған сұраулар алгоритмі

  1. Массивті префиксArray ретінде құрыңыз, оны 0 мәнімен инициализациялаңыз.
  2. Префиксінің соңғы элементінArray соңғы элементіне көшіріңіз массив берілген.
  3. Массивтен массивтен оңға солға қарай өтіп, берілген жиым элементінің көбейтіндісін және 2-нің қуаттарын сақтап, оныArray префиксімен қосыңыз.
  4. Сұранысты алыңыз, егер оң мән берілген массивтің соңғы индекс мәніне тең болмаса, онда префиксArray [сол жақ] және префиксArray [оң + 1] айырымының бөлінуін және 1 мен оңның ауысу әрекетін қайтарыңыз жиым индексі.
  5. Басқасы префикстің бөлінуін қайтарады [сол жақта] және массивтің 1 және оң индексінің жылжу әрекеті.

Екілік массивтің ішкі жиымдарының ондық мәндеріне арналған сұраныстарға түсініктеме

Мәселе туралы, екілік массивтің ішкі жиымдарының ондық мәндеріне сұраныстар берілген, a екілік массив және сол жақ индекс және оң индекс ретінде индекстер ауқымы. Берілген диапазонмен құрылған осы екілік санның ондық түрін табыңыз. Бізге диапазон берген сұраныс беріледі. Екілік саннан осылай құрылған ондық санды диапазонымен табу керек. Ол үшін біз массивтің ұзындығымен бірдей көлемдегі қосымша массив құрамыз. Біз сол массивті саламыз немесе сұранысты тұрақты уақытта шеше алуымыз үшін сол массивті алдын ала өңдеп, ондағы кейбір мәндерді толтыра аламыз деп айта аламыз.

Массив арқылы өтіңіз, бірақ массивті айналып өтпес бұрын, массивті 0-мен толтырыңыз. Java-да массив құрылған кезде ол автоматты түрде 0-мен толтырылады, бірақ C ++ тілінде біз мұны өз бетімізше жасауымыз керек. Осыдан кейін жиымның соңғы элементінің және 1-нің көбейтіндісін алыңыз, мәнді префикстің соңғы элементіне сақтаңызArray. Енді оңнан солға қарай бастаңыз, 2-ден бастау керек дегенді білдіредіnd массивтің соңғы элементі, енді 2 деңгейіндегі сандардың көбейтіндісін және берілген жиым элементін алып, оны алдыңғы префиксArray мәнімен қосыңыз. ОныArray префиксінің мәндерімен қосуды жалғастырыңыз және оныArray префиксінің тиісті орнына сақтаңыз.

Бізге берілген әрбір сұраныс үшін берілген дұрыс мән массивтің соңғы индексіне тең еместігін тексеріңіз. Егер ол дұрыс деп табылса, онда айырым префиксіArray [сол жақ] және [оң жақ] префиксі [оң] және оны ауыстыру операциясын 2 дәрежесінде қолданып, осы мәнді қайтарған кезде пайда болған мәнмен бөліңіз, әйтпесе айырмашылықты қайтарыңыз префиксіArray [сол жақ] және оны ауыстыру операциясымен оң мәнге бөліп, оны қайтарыңыз.

Іске асыру

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

Java бағдарламасы

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

Екілік массивтің ішкі массивтерінің ондық мәндеріне сұраныстардың күрделілігін талдау

Уақыттың күрделілігі

O (q) қайда «Q» - сұраныстар саны.

Ғарыштың күрделілігі

O (N) қайда «N» - бұл массивтегі элементтер саны.

анықтамалық