დაბეჭდეთ შეცვლილი მასივი შეკრებისა და გამოკლების ბრძანებების შესრულების შემდეგ


Რთული ტური საშუალო
ხშირად ეკითხებიან ByteDance Cisco Citrix უფასო დატენვა HackerRank ნაგარო ოპერისა Teradata
Array

თქვენ გეძლევათ 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 ტიპის მოთხოვნაა.

დაბეჭდეთ შეცვლილი მასივი შეკრებისა და გამოკლების ბრძანებების შესრულების შემდეგ

 

მრავალი მოთხოვნის შემდეგ შეცვლილი მასივის დასაბეჭდად ალგორითმი

  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 მნიშვნელობას. ამის შემდეგ, დაამატეთ მნიშვნელობა k დიაპაზონის საბოლოო წერტილის ინდექსში.

მოცემული თითოეული შეკითხვისთვის. აღნიშნული ტექნიკა უნდა შევასრულოთ. შემდეგ ჩვენ ვაშენებთ მასივს, რომელშიც მას შემდეგ მიმდინარე მნიშვნელობას დავამატებთ. და შეინახეთ თანხა მიმდინარე მნიშვნელობამდე. ან შეგვიძლია ვთქვათ, რომ განვაახლოთ მასივის მიმდინარე მნიშვნელობა. მასივის შექმნის შემდეგ, ჩვენ მასა ბეჭდავთ. ეს იქნება შეცვლილი მასივის სასურველი შედეგი.

კოდი

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

ჯავის კოდი შეცვლილი მასივის დასაბეჭდად შეკრებისა და გამოკლების ბრძანებების შესრულების შემდეგ

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

სირთულის ანალიზი

დროის სირთულე

O (q + n) სადაც "Q" არის შეკითხვების რაოდენობა და "ნ" არის მასივის ელემენტების რაოდენობა. რადგან ჯერ ვასრულებთ Q მოთხოვნებს, რომლებიც O (1) დროს იღებს და შემდეგ მასივის აგებას O (N) დრო სჭირდება.

სივრცის სირთულე

O (n) სადაც "ნ" არის მასივის ელემენტების რაოდენობა. მას შემდეგ, რაც შევქმენით მასივი ოპერაციების შესასრულებლად. სივრცის სირთულე ხაზოვანია.