စဉ်ဆက်မပြတ်အချိန်အကွာအဝေးတစ်ခုခင်းကျင်းအပေါ်စစ်ဆင်ရေး add


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် CodeNation DE ရှော နေခြည် Expedia Google
အခင်းအကျင်း Dynamic Programming

သင်တစ် ဦး ပေးပြီ ကိန်း အခင်းအကျင်း နှင့်အစကန ဦး အဖြစ် 0 အဖြစ်စတင်ခဲ့ပြီးအကွာအဝေးတစ်ခုကိုလည်းပေးခဲ့သည်။ တာဝန်ကတော့ပေးထားတဲ့နံပါတ်ကို array ရဲ့ range ထဲမှာထည့်ပြီးထွက်ပေါ်လာတဲ့ array ကို print ထုတ်ဖို့ပါပဲ။

နမူနာ

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

Query: {(0, 2, 50), (3, 4, 20), (1, 3, 30)}
50 80 80 50 20

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

50 ကို 0 in 2 သို့ array ထဲထည့်သွင်းသည်။ array သည်ဖြစ်လာလိမ့်မည် {50, 50, 50, 0, 0}

20 ကို 3 in 4 သို့ array ထဲထည့်သွင်းသည်။ array သည်ဖြစ်လာလိမ့်မည် {50, 50, 50, 20, 20}

30 ကို 1 in 3 သို့ array ထဲထည့်သွင်းသည်။ array သည်ဖြစ်လာလိမ့်မည် {50, 80, 80, 80, 20}

စဉ်ဆက်မပြတ်အချိန်အကွာအဝေးတစ်ခုခင်းကျင်းအပေါ်စစ်ဆင်ရေး add

 

algorithm

  1. အကွာအဝေး၏မေးမြန်းမှုတစ်ခုချင်းစီအတွက်အဆင့်များကိုလိုက်နာပါ။
    1. ပေးထားသောတန်ဖိုးကို array ၏ဘယ်ဘက်အညွှန်းတွင်ထည့်ပြီး၎င်းကိုသိမ်းထားပါ။
    2. တန်ဖိုးမှန်သည်နောက်ဆုံးခင်းကျင်းမှုအညွှန်းနှင့်မတူကိုစစ်ဆေးပါ၊ ထို့နောက်တန်ဖိုး၏ညာဘက် +၁ အနေအထားတွင်ပေးထားသောတန်ဖိုးကိုနှုတ်ယူပြီး၎င်းကိုသူ့ဟာသူသိုလှောင်ထားပါ။
  2. ခင်းကျင်းခြင်းမပြုလုပ်မီခင်းကျင်းမှုကိုဖြတ်သန်းသွားသည့်လမ်းကြောင်းအဖြစ်ယခင်စာရင်းနှင့်လက်ရှိတန်ဖိုးကိုထည့်သွင်းပြီး၎င်းကို array ၏တန်ဖိုးသို့သိမ်းဆည်းပါ။
  3. အဆင့်မြှင့်ပြီးနောက်, ရလဒ်ထွက်ခင်းကျင်းပုံနှိပ်ပါ။

စဉ်ဆက်မပြတ်အချိန်အကွာအဝေးအတွက်ရှင်းလင်းချက်တစ်ခုခင်းကျင်းအပေါ်စစ်ဆင်ရေးထည့်ပါ

တစ်ခုကိန်းသေနံပါတ်နှင့်ပေါင်းထည့်ရန်နံပါတ်ပေးထားသည်။ ကျနော်တို့ကိုလည်းစုံစမ်းမှုတစ်ခုအကွာအဝေးပေးထားသည်။ ၎င်းသည်အကွာအဝေး၏အစမှတ်နှင့်ဘယ်ဘက်အစရှိသည်နှင့်အကွာအဝေး၏အဆုံးမှတ်ကိုမှန်ကန်သော။ ပေးထားသောအကွာအဝေးတွင်ပေးထားသောနံပါတ်ကိုဖြစ်နိုင်သမျှကိန်းများထပ်ပေါင်းထည့်ရန်ကျွန်ုပ်တို့အားတောင်းဆိုခဲ့သည်။ နောက်ဆုံးရလဒ်ထွက်ပေါ်လာတဲ့ array ကို print ထုတ်ပါ။ ဤအတွက်၊ ကျွန်ုပ်တို့သည်အပိုဆောင်းလုပ်ဆောင်မှုကိုအလွန်ပြုပြင်ထားသောနည်းလမ်းဖြင့်လုပ်ဆောင်သွားမည်။ လက်ဝဲနှင့်ညာ +1 နေရာတွင်ခင်းကျင်းပြသခြင်းနှင့်၎င်းခင်းကျင်းမှုအားမွမ်းမံခြင်းမပြုမီ array index တန်ဖိုးများကိုပေးထားသည့်တန်ဖိုးနှင့်ဖြည့်ပါလိမ့်မည်။

ပေးထားသောစုံစမ်းမှုတစ်ခုစီအတွက်ဘယ်ဘက်နှင့်လက်ဝဲဘက်ကျွန်ုပ်တို့သည်ပေးထားသောတန်ဖိုးကိုလက်ဝဲဘက်ရှိအညွှန်းတွင်ထပ်ထည့်မည်၊ လက်ဝဲအညွှန်းတွင်သာသတိရပါ။ ပြီးတော့မှန်ကန်တဲ့တန်ဖိုးအတွက်တော့ value က array ရဲ့နောက်ဆုံးအညွှန်းကိန်းနဲ့မညီဘူးလားဆိုတာစစ်ဆေးပါမယ်၊ ပေးထားတဲ့အခြေအနေကကျေနပ်ပြီဆိုရင်၊ ငါတို့ပေးထားတဲ့တန်ဖိုးအညွှန်းကိုမွမ်းမံမယ်၊ ပေးထားတဲ့တန်ဖိုးကိုကနေနုတ်ပါမယ်။ စစ်ခင်းကျင်း၏ညာဘက်အညွှန်းကိန်းများနှင့်ခင်းကျင်းသူ့ဟာသူ၏ညာဘက်အနေအထားအညွှန်းကိန်းမှသိမ်းထားပါ။ စုံစမ်းမှုတိုင်းအတွက်ကျွန်ုပ်တို့သည်ဤစစ်ဆင်ရေးများကိုလုပ်ဆောင်တော့မည်ဖြစ်သည်။

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

ကုဒ်

စဉ်ဆက်မပြတ်အချိန်အပိုင်းအခြားအတွက် C ++ တွင်အကောင်အထည်ဖော်ခြင်းသည် array ပေါ်တွင်စစ်ဆင်ရေးကိုထည့်ပါ

#include<iostream>

using namespace std;

void update(int arr[], int N)
{
    for (int i = 1; i < N; i++)
        arr[i] += arr[i - 1];
}

void addOperation(int arr[], int N, int left, int right, int value)
{
    arr[left] += value;
    if (right != N - 1)
        arr[right + 1] -= value;
}

void printArray(int arr[], int N)
{
    update(arr, N);
    for (int i = 0; i < N; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main()
{
    int N = 5;

    int arr[N] = {0};

    addOperation(arr, N, 0, 2, 50);
    addOperation(arr, N, 3, 4, 20);
    addOperation(arr, N, 1, 3, 30);

    printArray(arr, N);
    return 0;
}
50 80 80 50 20

Constant time range အတွက် Java တွင်အကောင်အထည်ဖော်ခြင်းသည် array တစ်ခုအတွင်းလည်ပတ်မှုထပ်တိုးစေသည်

class AddOperation
{
    static void update(int arr[], int N)
    {
        for (int i = 1; i < N; i++)
            arr[i] += arr[i - 1];
    }
    static void addOperation(int arr[], int N, int left, int right, int value)
    {
        arr[left] += value;
        if (right != N - 1)
            arr[right + 1] -= value;
    }
    static void printArray(int arr[], int N)
    {
        update(arr, N);

        for (int i = 0; i < N; i++)
            System.out.print(""+arr[i]+" ");
        System.out.print("\n");
    }
    public static void main (String[] args)
    {
        int N = 5;

        int arr[] = new int[N];

        addOperation(arr, N, 0, 2, 50);
        addOperation(arr, N, 3, 4, 20);
        addOperation(arr, N, 1, 3, 30);
        printArray(arr, N);
    }
}
50 80 80 50 20

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

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

အို (N + Q) ဘယ်မှာ "N" သည် array ထဲရှိ element အရေအတွက်နှင့်ဖြစ်သည် "မေး" မေးမြန်းချက်များ၏နံပါတ်ဖြစ်ပါတယ်။ အဘယ်ကြောင့်ဆိုသော်ကျွန်ုပ်တို့သည် left index တွင်တန်ဖိုးကိုတိုးမြှင့်ခဲ့ပြီး၎င်းသည် array ၏နယ်နိမိတ်ရှိလျှင်ညာဘက် +1 အညွှန်းတွင်တန်ဖိုးကိုလျှော့ချထားသောကြောင့်ဖြစ်သည်။

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

အို (N) ဘယ်မှာ "N" သည် array အတွင်းရှိ element အရေအတွက်ဖြစ်သည်။