Երկուական զանգվածի ենթածրագրերի տասնորդական արժեքների հարցումներ  


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Amazon Google
Դասավորություն Հարցման խնդիր

Տրված երկուական զանգվածի ենթածրագրերի տասնորդական արժեքների հարցումներ գրել: Խնդրի հայտարարությունը խնդրում է պարզել տասնորդական համարը, որը այդքան ձևավորվել է տիրույթի օգնությամբ, երկուական զանգվածում:

Օրինակ  

Մուտք:

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

Հարցում (1, 5)

Հարցում (3, 6)

Արդյունք:

12 9

Բացատրությունը.

Արդյունքը, որը ձևավորվել է որպես երկուական թվեր, որոնք ներկայացնում են 1-ից 5-ը ներառյալ (01100) սահմաններում, 12 է:

Արդյունքն այնպես է ձևավորվել, ինչպես երկուական թվեր ներկայացնելով 3-ից 6-ը ներառյալ (1001) սահմաններում, 9-ն է:

Երկուական զանգվածի ենթաշեղերի տասնորդական արժեքների հարցումներPin

 

Երկուական զանգվածի ենթաշեղերի տասնորդական արժեքների հարցումների ալգորիթմ  

  1. Ստեղծեք զանգված որպես նախածանց Array, նախնականացրեք այն 0-ով:
  2. Պատճենել Arr- ի նախածանցի վերջին տարրը վերջինի տարրին դասավորություն տրված
  3. Traանցի միջով անցեք զանգվածի աջից ձախ և պահեք տրված զանգվածի տարրի արտադրանքը և 2-ի հզորությունները և ավելացրեք այն Array նախածանցով:
  4. Ստացեք հարցումը, եթե աջի արժեքը հավասար չէ տվյալ զանգվածի վերջին ինդեքսային արժեքին, վերադարձեք Array [ձախ] և Array նախածանցի տարբերության բաժինը [աջ + 1] և 1-ի և աջի հերթափոխի գործողությունը զանգվածի ցուցիչ
  5. Ուրիշը վերադարձրեք Array նախածանցի բաժանումը [ձախից] և զանգվածի 1-ի և աջ ցուցիչի հերթափոխի գործողությունը:
Տես նաեւ,
Վերծանել տողը

Երկուական զանգվածի ենթաշարքերի տասնորդական արժեքների հարցումների բացատրություն  

Ինչ վերաբերում է երկուական զանգվածի ենթաշեղերի տասնորդական արժեքների հարցմանը, տրված ա երկուական զանգված և մի շարք ինդեքսներ ՝ որպես ձախ ինդեքս և աջ ինդեքս: Գտեք տրված տիրույթի հետ այդքան կազմված տրված երկուական համարի տասնորդական ձևը: Մեզ կտրվի հարցում, որում մենք տվել ենք ընդգրկույթ: Մենք պետք է գտնենք երկուական թվից այդքան կազմված տասնորդական համարը ՝ տիրույթով: Դրա համար մենք պատրաստվում ենք ստեղծել չափի լրացուցիչ զանգված, որը հավասար է զանգվածի երկարությանը: Մենք կկառուցենք այդ զանգվածը, կամ կարող ենք ասել, որ կարող ենք նախապատրաստել այդ զանգվածը և լրացնել դրա մեջ որոշ արժեքներ, որպեսզի կարողանանք հարցումը լուծել մշտական ​​ժամանակում:

Անցեք զանգվածի միջով, բայց զանգվածը անցնելուց առաջ զանգվածը լցրեք 0. Այն դեպքում, երբ զանգվածը ստեղծվում է, այն ավտոմատ կերպով լցվում է 0-ով, բայց C ++ - ում մենք դա պետք է անենք ինքնուրույն: Դրանից հետո ստացեք զանգվածի վերջին տարրի և 1-ի արտադրանքը, պահպանեք արժեքը Array- ի նախածանցի վերջին տարրի մեջ: Այժմ սկսեք աջից ձախ, նշանակում է սկսել 2-իցnd զանգվածի վերջին տարրը, այժմ ստացիր 2-ի ուժ ունեցող թվերի արտադրյալը և տրված զանգվածի տարրը և ավելացրու այն Array զանգվածի նախածանցի նախորդ արժեքով: Շարունակեք ավելացնել այն prefixArray- ի արժեքներով և պահեք այն Array- ի նախածանցի համապատասխան տեղում:

Տես նաեւ,
Տրված տիրույթի արժեքներով զանգվածի տարրերի հաշվարկի հարցումներ

Մեզ տրված յուրաքանչյուր հարցման համար ստուգեք, արդյոք տրված ճիշտ արժեքը հավասար չէ զանգվածի վերջին ինդեքսին: Եթե ​​պարզվում է, որ դա ճիշտ է, ապա ստացիր տարբերության նախածանց Array [ձախ] և prefixArray [աջ] և բաժանել այն արժեքի հետ, որը այդպես է կազմված, երբ հերթափոխի գործողությունը կիրառում ենք 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

Երկուական զանգվածի ենթածրագրերի տասնորդական արժեքների հարցումների բարդության վերլուծություն  

Timeամանակի բարդություն

Ո (ք) որտեղ "Q" հարցումների քանակն է:

Տես նաեւ,
Ներդիրի տեսակավորում

Տիեզերական բարդություն

O (n) որտեղ «Ն» զանգվածում տարրերի քանակն է:

Մանրամասն