ဖြည့်စွက်ခြင်းနှင့်နုတ်ခြင်း၏အမိန့်ကိုစီရင်ပြီးနောက်ပြုပြင်ထားသောခင်းကျင်းပုံနှိပ်ပါ


ခက်ခဲအဆင့် အလယ်အလတ်
မကြာခဏမေးတယ် ByteDance Cisco သည် Citrix FreeCharge HackerRank နာဂ တေးသံစုံကဇါတ် Teradata
အခင်းအကျင်း

သင့်အားအရွယ်အစား n ခင်းကျင်းမှုတစ်ခုပေးထားသည်။ အစပိုင်းတွင် array အတွင်းရှိတန်ဖိုးများအားလုံးသည် 0 ဖြစ်လိမ့်မည်။ query တစ်ခုစီတွင်တန်ဖိုး ၄ ခု၊ query T အမျိုးအစား၊ အကွာအဝေး၏ဘယ်ဘက်အမှတ်၊ အကွာအဝေး၏ညာဘက် point နှင့်နံပါတ် k တို့ပါဝင်သည်။ သင်သည်အောက်ပါလုပ်ဆောင်မှုများကိုလုပ်ဆောင်ရမည်။

အကယ်၍ T = 0 ဖြစ်ပါကပေးထားသောခင်းကျင်းချက် (start, end) အတွင်းရှိကိန်းအားလုံးအတွင်းသို့တန်ဖိုး k ထည့်ပါ။

အကယ်၍ T = 1 ဆိုပါကပေးထားသောခင်းကျင်းချက်အတွင်း (start, end) အတွင်းရှိကိန်းအားလုံး၏တန်ဖိုးမှ 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) သည် type 1 query ဖြစ်သဖြင့်အကွာအဝေးအတွင်းရှိကိန်းအားလုံးကို 0 ထည့်ပါ။

(1, 3, 5, 2) သည် type 2 query တစ်ခုဖြစ်သဖြင့်အကွာအဝေးအတွင်းရှိအားလုံးမှ 1 ကိုနုတ်ပါ။

(0, 1, 4, 3) သည် type 3 query ဖြစ်သဖြင့်အကွာအဝေးအတွင်းရှိကိန်းအားလုံးကို 0 ထည့်ပါ။

ဖြည့်စွက်ခြင်းနှင့်နုတ်ခြင်း၏အမိန့်ကိုစီရင်ပြီးနောက်ပြုပြင်ထားသောခင်းကျင်းပုံနှိပ်ပါ

 

မျိုးစုံမေးမြန်းမှုပြီးနောက်ပြုပြင်ထားသောခင်းကျင်းမှုကိုပုံနှိပ်ရန် Algorithm

  1. အစပြုပါ အခင်းအကျင်း 0 နှင့်အတူ။
  2. မေးမြန်းမှုတစ်ခုစီအတွက်
  3. type query query သည် value များထည့်ရန်ဖြစ်လျှင် left-1 အနေအထားရှိ value ကို k ထပ်ထည့်ပြီး right အနေအထားတွင်တန်ဖိုး k ကိုနုတ်ပါ။
  4. အကယ်၍ type query သည်တန်ဖိုးများကိုနုတ်လျှင်၊ left-1 အနေအထားရှိ value ကို k ကိုနုတ်ခြင်းနှင့်ညာဘက်အနေအထားတွင်တန်ဖိုး k ကိုထည့်ပါ။
  5. Array ကိုဖြတ်ပြီးယခင်တန်ဖိုးတစ်ခုစီကိုလက်ရှိတန်ဖိုး၏တန်ဖိုးသို့ထည့်ပါ။
  6. နောက်ဆုံးခင်းကျင်းပုံနှိပ်ပါ။

ရှင်းလင်းချက်

အစပိုင်းမှာတော့ array ထဲမှာရှိတဲ့တန်ဖိုးတွေအားလုံးဟာ 0 ဖြစ်တယ်။ ငါတို့ကိုလည်း a နဲ့ပေးတယ် q မေးမြန်းချက်အရေအတွက်၊ စုံစမ်းမှုသည်အမျိုးအစားနှစ်မျိုးရှိလိမ့်မည်။ တစ်ခုချင်းစီတွင်ရှာဖွေမှုတစ်ခုစီပါ ၀ င်သည်။ ယင်းအမျိုးအစား၊ အကွာအဝေးနှင့်နံပါတ် k ။ အကယ်၍ မေးမြန်းမှုအမျိုးအစားသည် 0 ဖြစ်ပါကကျွန်ုပ်တို့သည်အကွာအဝေးအတွင်းရှိကိန်းအားလုံး၏တန်ဖိုးသို့ k ထည့်ပါလိမ့်မည်။ အကယ်၍ ကျွန်တော်တို့က query ကို 1 အဖြစ်ပေးမယ်ဆိုလျှင်ကိန်းတန်းအားလုံးအတွင်းကိန်းတန်ဖိုးအားလုံးကိုနုတ်ပါလိမ့်မယ်။ မေးမြန်းချက်အားလုံးပြီးသွားရင်အဲ့ဒီ array ကိုပုံနှိပ်လိမ့်မယ်။

ဤအစစ်ဆင်ရေးဖျော်ဖြေသည်။ ပထမ ဦး စွာကျွန်ုပ်တို့အားမည်သည့်စုံစမ်းမှုအမျိုးအစားပေးသည်ကိုစစ်ဆေးရန်လိုအပ်သည် အကယ်၍ စုံစမ်းမှုသည်ပထမအမျိုးအစားဖြစ်ပါကကျွန်ုပ်တို့သည်တန်ဖိုးကို k ကို array အတွင်းရှိအကွာအဝေး၏စမှတ်သို့ထည့်ပါ။ ဒါ့အပြင် value ကို array ရဲ့ range point ကနေနုတ်ပါ။

ကျနော်တို့ယခင်ကဖော်ပြခဲ့တဲ့ technique ကို၏ဆန့်ကျင်ဘက်ပြုလိမ့်မည်။ အကယ်၍ ကျွန်ုပ်တို့သည် type 1 query ကိုအသုံးပြုရန်ပေးထားပါကကျွန်ုပ်တို့သည် range အတွင်းရှိ integer array ၏တန်ဖိုးများအားလုံးကိုနုတ်ရန်ဖြစ်သည်။ ထိုအခါကျွန်ုပ်တို့သည်တန်ဖိုးတစ်ခု k ကို array တစ်ခု၏စတင်အကွာအဝေးတန်ဖိုးမှနုတ်ပါလိမ့်မည်။ ပြီးနောက်, အကွာအဝေး၏ endpoint အညွှန်းကိန်းမှာတန်ဖိုး k ထည့်သွင်းပါ။

ပေးထားသောမေးမြန်းချက်တစ်ခုချင်းစီအတွက်။ ကျနော်တို့ဖော်ပြခဲ့တဲ့ technique ကိုဖျော်ဖြေဖို့ရှိသည်။ ထိုအခါကျွန်ုပ်တို့သည် array ကိုတည်ဆောက်မည်ဖြစ်သည်၊ ၎င်းသည်ယခင်တန်ဖိုးကိုလက်ရှိတန်ဖိုး၏တန်ဖိုးသို့ပေါင်းထည့်မည်ဖြစ်သည်။ နှင့်ပေါင်းလဒ်သည်လက်ရှိတန်ဖိုးသိုလှောင်ထားပါ။ ဒါမှမဟုတ်ကျနော်တို့က array ၏လက်ရှိတန်ဖိုးကို update လုပ်တယ်လို့ပြောနိုင်တယ်။ Array ကိုတည်ဆောက်ပြီးတာနဲ့ကျွန်တော်တို့က array ကိုပုံနှိပ်မှာပါ။ ဒါကပြုပြင်ထားသောခင်းကျင်းမှု၏လိုချင်သောရလဒ်ဖြစ်လိမ့်မည်။

ကုဒ်

ဖြည့်စွက်ခြင်းနှင့်နုတ်ခြင်း၏အမိန့်များကိုစီရင်ပြီးနောက်ပြုပြင်ထားသောခင်းကျင်းမှုကို print ထုတ်ရန် 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

ဖြည့်စွက်ခြင်းနှင့်နုတ်ခြင်းအမိန့်များကိုစီရင်ပြီးနောက်ပြုပြင်ထားသောခင်းကျင်းမှုကို print ထုတ်ရန် 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

ရှုပ်ထွေးဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (q + n) ဘယ်မှာ "မေး" မေးမြန်းချက်အရေအတွက်နှင့် “ n” သည် array အတွင်းရှိ element အရေအတွက်ဖြစ်သည်။ အဘယ်ကြောင့်ဆိုသော် ဦး စွာကျွန်ုပ်တို့သည် O (1) အချိန်ယူပြီးခင်းကျင်းခြင်းများပြုလုပ်သော Q မေးမြန်းမှုများကိုလုပ်ဆောင်သောကြောင့် O (N) အချိန်လိုအပ်သည်။

အာကာသရှုပ်ထွေးမှု

အို (ဎ) ဘယ်မှာ “ n” သည် array အတွင်းရှိ element အရေအတွက်ဖြစ်သည်။ ကျနော်တို့အပေါ်စစ်ဆင်ရေးလုပ်ဆောင်ရန်တစ်ခုခင်းကျင်းဖန်တီးကတည်းက။ အဆိုပါအာကာသရှုပ်ထွေး linear ဖြစ်ပါတယ်။