Տպեք փոփոխված զանգվածը ՝ գումարման և հանումի հրամանները կատարելուց հետո  


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են ByteDance Cisco Citrix Անվճար լիցքավորում HackerRank Նագարո Օպերա Տերադատա
Դասավորություն

Ձեզ տրվում է n չափի զանգված, սկզբում զանգվածում բոլոր արժեքները կլինեն 0, և հարցումները: Յուրաքանչյուր հարցում պարունակում է չորս արժեք, հարցման տեսակ T, տիրույթի ձախ կետ, միջակայքի աջ կետ և k թիվ, դուք պետք է կատարեք հետևյալ գործողությունները.

Եթե ​​T = 0, տրված տիրույթում (սկիզբ, ավարտ) բոլոր ամբողջ թվերին ավելացնել k արժեքը,

Եթե ​​T = 1, տրված զանգվածում հանված k արժեքը տրված տիրույթում գտնվող բոլոր ամբողջ թվերից (սկիզբ, ավարտ),

Օրինակ  

arr[]={0, 0, 0, 0, 0}
Query: {(0, 2, 4, 1), (1, 3, 5, 2), (0, 1, 4, 3)}
3 4 2 2 -2

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

(0, 2, 4, 1) ավելացնել 1-ը տիրույթի բոլոր ամբողջ թվերին, քանի որ 0 տիպի հարցում է:

(1, 3, 5, 2) միջակայքի բոլոր ամբողջ թվերից հանել 2-ը, քանի որ դա 1-ին տիպի հարցում է:

(0, 1, 4, 3) ավելացնել 3-ը տիրույթի բոլոր ամբողջ թվերին, քանի որ 0 տիպի հարցում է:

Տպեք փոփոխված զանգվածը ՝ գումարման և հանումի հրամանները կատարելուց հետոPin  

 

Բազմաթիվ հարցումներից հետո փոփոխված զանգվածը տպելու ալգորիթմ  

  1. Նախաձեռնեք դասավորություն 0- ի հետ:
  2. Յուրաքանչյուր հարցման համար
  3. Եթե ​​հարցման տիպը արժեքներ ավելացնելու համար է, ապա արժեքը թարմացրեք ձախ -1 դիրքում `ավելացնելով k արժեքը և ճիշտ դիրքում հանել k արժեքը:
  4. Եթե ​​հարցման տիպը պետք է հանի արժեքները, ապա թարմացրու արժեքը ձախ -1 դիրքում ՝ հանելով k արժեքը և աջ դիրքում ավելացնել k արժեքը:
  5. Անցեք զանգվածը և յուրաքանչյուր նախորդ արժեք ավելացրեք զանգվածի ընթացիկ արժեքին:
  6. Տպեք վերջին զանգվածը:
Տես նաեւ,
Տպիր Ֆիբոնաչիի համարները հակառակ հերթականությամբ

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

Մեզ զանգված է տրված, ի սկզբանե, զանգվածում բոլոր արժեքներն են 0. Մեզ նաև տրամադրվում է a q հարցումների քանակը, հարցումը կլինի երկու տեսակի. յուրաքանչյուր հարցում պարունակում է, դրա տեսակը, ընդգրկույթը և k թիվը: Եթե ​​հարցման տեսակը 0 է, ապա մենք բոլոր արժեքներին կավելացնենք k արժեքը, որոնք ընդգրկում են տիրույթը: Եթե ​​հարցման տեսակը մեզ տրվի 1-ով, մենք միջակայքում կհանենք k արժեքը բոլոր ամբողջ թվերից: Բոլոր հարցումները կատարելուց հետո մենք կտպագրենք այդ արդյունքի զանգվածը:

Այս գործողությունները կատարելու համար: Նախ պետք է ստուգենք, թե ինչ տեսակի հարցում է մեզ տրվում: Եթե ​​հարցումը առաջին տիպի է, ապա զանգվածում տիրույթի սկզբնական կետին ավելացնում ենք k արժեքը: Բացի այդ, k արժեքը հանեք զանգվածի տիրույթի ավարտական ​​կետից:

Մենք կանենք նախկինում նշված տեխնիկայի հակառակը: Եթե ​​մեզ տրված է օգտագործել 1-ին տիպի հարցումը, որի ընթացքում մենք պետք է հանենք ամբողջ զանգվածի բոլոր արժեքները տիրույթում: Դրանից հետո մենք զանգվածը կհանենք զանգվածի մեկնարկային միջակայքի արժեքից: Դրանից հետո միջակայքի վերջնական ցուցիչում ավելացրեք k արժեքը:

Տրված հարցումներից յուրաքանչյուրի համար: Մենք պետք է կատարենք նշված տեխնիկան: Դրանից հետո մենք կկառուցենք զանգված, որում նախորդ զանգվածը կավելացնենք զանգվածի ընթացիկ արժեքին: Եվ գումարը պահեք ընթացիկ արժեքին: Կամ կարող ենք ասել, որ մենք թարմացնում ենք զանգվածի ընթացիկ արժեքը: Buildingանգվածը կառուցելուց հետո մենք կ տպենք զանգվածը: Դա կլինի փոփոխված զանգվածի ցանկալի արդյունքը:

Տես նաեւ,
Ընկերներ զուգավորման խնդիր

Կոդ  

C ++ կոդ ՝ լրացման և հանումի հրամանները կատարելուց հետո փոփոխված զանգվածը տպելու համար

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

using namespace std;

void solveQuery(int arr[], int n, int T, int left, int right, int k)
{
    if (T == 0)
    {
        arr[left -1] += k;
        arr[right] += -k;
    }
    else
    {
        arr[left -1] += -k;
        arr[right] += k;
    }
    return;
}

void build(int arr[], int n)
{
    for (int i = 1; i < n; ++i)
        arr[i] += arr[i-1];

    return;
}

int main()
{
    int n = 5;
    int arr[n+1];

    memset(arr, 0, sizeof(arr));


    //query, left, right, k(value which is to add or subtract.
    solveQuery(arr, n, 0, 2, 4, 1);

    //query, left, right, k(value which is to add or subtract.
    solveQuery(arr, n, 1, 3, 5, 2);

    //query, left, right, k(value which is to add or subtract.
    solveQuery(arr, n, 0, 1, 4, 3);

    build(arr, n);

    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";
    return 0;
}
3 4 2 2 -2

Java կոդ ՝ լրացման և հանումի հրամանները կատարելուց հետո փոփոխված զանգվածը տպելու համար

import java.util.Arrays;

class AdditionSubtractionQuery
{
    static void solveQuery(int arr[], int n, int T, int left, int right, int k)
    {
        if (T == 0)
        {
            arr[left -1] += k;
            arr[right] += -k;
        }
        else
        {
            arr[left -1] += -k;
            arr[right] += k;
        }
        return;
    }
    
    static void build(int arr[], int n)
    {
        for (int i = 1; i < n; ++i)
            arr[i] += arr[i-1];
    }
    
    public static void main(String arg[])
    {
        int n = 5;
        int arr[] = new int[n+1];
        Arrays.fill(arr, 0);

        //query, left, right, k(value which is to add or subtract.
        solveQuery(arr, n, 0, 2, 4, 1);

        //query, left, right, k(value which is to add or subtract.
        solveQuery(arr, n, 1, 3, 5, 2);

        //query, left, right, k(value which is to add or subtract.
        solveQuery(arr, n, 0, 1, 4, 3);

        build(arr, n);

        for (int i = 0; i < n; ++i)
            System.out.print(arr[i]+" ");
    }
}
3 4 2 2 -2

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

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

O (q + n) որտեղ "Q" հարցումների քանակն է, և «Ն» զանգվածում տարրերի քանակն է: Քանի որ նախ մենք կատարում ենք Q հարցումներ, որոնք տևում են O (1) ժամանակ, իսկ հետո զանգվածի կառուցման համար պահանջվում է O (N) ժամանակ:

Տես նաեւ,
Լարով գտեք տեղադրված փակագծի առավելագույն խորությունը

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

O (n) որտեղ «Ն» զանգվածում տարրերի քանակն է: Քանի որ մենք ստեղծեցինք զանգված ՝ գործողությունները կատարելու համար: Տիեզերական բարդությունը գծային է: