Առանց թարմացումների ընդգրկեք հարցումների քանակը  


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Blackrock GE Healthcare Moonfrog լաբորատորիաներ Սինոփսիս Taxi4Sure- ը Twilio
Դասավորություն Larsen & Toubro Հարցման խնդիր

Խնդիրի հայտարարություն  

«Առանց թարմացումների միջակայքի գումարի հարցումներ» խնդրի մեջ նշվում է, որ դուք ունեք դասավորություն of ամբողջական թվերը և մի շարք: Խնդրի հայտարարությունը խնդրում է պարզել տրված տիրույթում գտնվող բոլոր տարրերի հանրագումարը:

Օրինակ  

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

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

բացատրություն

(0, 4) ընդգրկույթի միջև ներառված բոլոր թվերի հանրագումարը 40 է, իսկ միջակայքի (1, 3) ներառյալ բոլոր թվերի հանրագումարը `24:

Առանց թարմացումների ընդգրկեք հարցումների քանակըPin

 

Ալգորիթմ  

  1. Ստեղծեք զանգվածի հավաքածուի չափի զանգված, որը հավասար է տրված զանգվածին:
  2. Անցեք տրված զանգվածի միջով և պահեք sumArray- ի նախորդ տարրի և տրված զանգվածի ընթացիկ տարրի գումարը և պահեք այն sumArray- ում:
  3. Յուրաքանչյուր հարցման համար, եթե ձախը հավասար է 0-ի, ապա վերադարձիր sumArray- ը [աջ],
  4. Ուրիշը վերադարձիր sumArray [աջ] - sumArray [ձախ - 1]:

բացատրություն  

Մենք տվել ենք ամբողջ թվերի և տիրույթի զանգված, մեզ խնդրել են յուրաքանչյուր հարցումի համար պարզել տվյալ տիրույթում գտնվող բոլոր տարրերի հանրագումարը: Հարցումներից յուրաքանչյուրը բաղկացած է մի տիրույթից, որպես տիրույթի մեկնարկի և ավարտի կետ: Այս հարցը չի ներառում որևէ թարմացման հարցում: Դա նշանակում է, որ հարցման պատասխանը պարզելիս անհրաժեշտ չէ որևէ բան թարմացնել: Մենք պարզապես կկառուցենք տրված զանգվածը այնպես, որ 0 տարրից մինչև ընթացիկ ինդեքս բոլոր տարրերի հանրագումարը լինի կառուցված զանգվածի ith դիրքում: Այսպիսով, յուրաքանչյուր հարցում կլուծվի O (1) -ում, O (n) լրացուցիչ տարածությամբ:

Տես նաեւ,
Գտեք N եզակի ամբողջ թվերի հանրագումար մինչև զրո Leetcode լուծում

Մենք կկառուցենք մեր ստեղծած գումարման զանգվածը: Այս sumArray- ում 0-ից i տարրերի հանրագումարը կպահպանվի sumArray- ի երկրորդ դիրքում: Մենք դա հաշվարկելու ենք, քանի որ գումարել ենք sumArray- ի նախորդ արժեքը և տվյալ զանգվածի ընթացիկ արժեքը և անցնելիս այն պահում ենք sumArray- ի ընթացիկ ինդեքսային դիրքում: Այսպիսով, երբ ինչ-որ մեկը հարցրեց, թե որն է այս դիրքի բոլոր թվերի հանրագումարը, մենք պարզապես պետք է վերադարձնենք այդ դիրքի արժեքը յուրաքանչյուր յուրահատուկ զանգվածի համար:

Երբ մենք կստանանք որևէ միջակայքից բաղկացած հարցում, և եթե գտնենք, որ միջակայքի ձախ կամ ելակետը հավասար է 0-ի, մենք պարզապես կվերադարձնենք sumArray- ի արժեքը [աջ], ինչը վերը քննարկեցինք, ձախ միջակայքն է 0-ին հավասար չէ, մենք կվերադարձնենք sumArray [աջ] և sumArray [ձախ -1] տարբերությունները: Դրանք կպահանջվեն պատասխաններ: Այս մոտեցումը նաև ամենահեշտ ձևերից մեկն է, որով մենք օգտագործում ենք Դինամիկ ծրագրավորում.

Կոդ  

Առանց թարմացումների Range գումարի հարցումների համար 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 գումարի հարցումների Java կոդ

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

Բարդության վերլուծություն  

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

O (N + Q),  քանի որ մեզ անհրաժեշտ է O (N) ՝ յուրաքանչյուր հարցման համար sumArray- ի և ապա O (1) ժամանակը հաշվարկելու համար:

Տես նաեւ,
Գտեք չորս տարր, որոնք գումարվում են տվյալ արժեքի (Hashmap)

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

Տրված մոտեցման մեջ մենք ստեղծել ենք նոր զանգված sumArray ՝ տարրերի գումարը 0-ից i պահելու համար: Այսպիսով, այս մոտեցումը պահանջում է ՎՐԱ) տարածություն Բայց մենք կարող էինք նաև փոփոխել սկզբնական զանգվածը: Այդ ժամանակ տիեզերական բարդությունը կվերածվեր հաստատականի: