အားလုံးထူးဆန်းအရှည် Subarrays Leetcode ဖြေရှင်းချက်၏ပေါင်းလဒ်


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် LinkedIn တို့
အခင်းအကျင်း

ပြProbleနာဖော်ပြချက်

ဤပြproblemနာတွင်အပေါင်းကိန်းများပေးသည်။ ပေးထားသောခင်းကျင်းမှုတစ်ခု၏ဖြစ်နိုင်ခြေထူးဆန်းသည့်အရှုံးခွဲငယ်များ၏စုစုပေါင်းတစ်ခုတည်းကိုတွက်ချက်ခြင်းနှင့်ပြန်ပို့ခြင်းတို့ပြုလုပ်ရမည်။ subarray သည်ဆက်တိုက်ဆက်တိုက်ဖြစ်သည် အခင်းအကျင်း.

နမူနာ

arr = [1,4,2,5,3]
58

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

ထူးဆန်းသော arr ၏ subarrays နှင့် ၄ င်းတို့၏ပမာဏမှာ -
[1] = 1, [4] = 4, [2] = 2, [5] = 5, [3] = 3, [1,4,2] = 7, [4,2,5] = 11, [2,5,3] = 10, [1,4,2,5,3] = 15
ဤအရာအားလုံးကိုပေါင်းခြင်းဖြင့် 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58 ရတယ်

arr = [1,2]
3

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

subartays ၂ ခုသာထူးဆန်းသည်။ [2] နှင့် [1] ။ သူတို့ရဲ့ပေါင်းလဒ်က 2 ။

ချဉ်းကပ်နည်း (Brute Force)

ဤပြproblemနာကို brute force ဖြင့်ဖြေရှင်းရန်အတွက်ကျွန်ုပ်တို့သည်ထူးဆန်းသောအရှည် subarrays များအားလုံးကိုသွားပြီးစုစုပေါင်းပေါင်းလဒ်ကိုတွက်ချက်ပြီးပြန်ပို့ရန်လိုအပ်သည်ကိုပြသနာမှတွေ့မြင်ရန်အလွန်လွယ်ကူသည်။
ကျွန်ုပ်တို့သည်ဤအရာကိုရိုးရှင်းသောအဆင့်များဖြင့်လုပ်ဆောင်နိုင်သည်။

၁။ variable တစ်ခုကိုဖန်တီးပါ ငှေပေါငျး စုစုပေါင်းပေါင်းလဒ်ကိုသိုလှောင်ရန်။
၂။ ထံမှစတင်သောထူးဆန်းသည့်အရှည် subarrays များအတွက် for loop ကိုဖွင့်ပါ Len= 1 နှင့် 2 နေစဉ်တန်ဖိုးတိုးလာစောင့်ရှောက်လော့ Len <= n (အခင်းကျင်း၏အရွယ်အစား) ။
၃။ ဒီကွင်းဆက်ထဲမှာ၊ a ကို Run ပါ ကွင်းဆက် i = 0 မှ i = n-len သို့ subarray ၏အနေအထားကိုစတင်ဘို့။
၄။ အပေါ်က loop ထဲမှာဒီ subarray အတွက် loop ကိုဖွင့်ပါ၊ အညွှန်းကိန်းက i မှစပြီး i + မှာအဆုံးသတ်သည်Len-1 နှင့်ဤ subarray ၏ element အားလုံးထည့်ပါ။
5. နောက်ဆုံးမှာပြန်လာပါ ငှေပေါငျး.

အားလုံးထူးဆန်းအရှည် Subarrays Leetcode ဖြေရှင်းချက်၏ Sum ၏အကောင်အထည်ဖော်မှု

C ++ အစီအစဉ်

#include <bits/stdc++.h>
using namespace std;

int sumOddLengthSubarrays(vector<int>& arr) 
{
    int sum=0;
    int n=arr.size();

    for(int len=1;len<=n;len+=2)
        for(int i=0;i<n-len+1;i++)
            for(int j=i;j<i+len;j++) 
                sum+=arr[j];
    
    return sum;
}

int main() 
{
    vector<int> arr = {1,4,2,5,3};
  
  cout<<sumOddLengthSubarrays(arr)<<endl;

  return 0; 
}
58

Java အစီအစဉ်

#include <bits/stdc++.h>
using namespace std;

int sumOddLengthSubarrays(vector<int>& arr) 
{
    int sum=0;
    int n=arr.size();

    for(int len=1;len<=n;len+=2)
        for(int i=0;i<n-len+1;i++)
            for(int j=i;j<i+len;j++) 
                sum+=arr[j];
    
    return sum;
}

int main() 
{
    vector<int> arr = {1,4,2,5,3};
  
  cout<<sumOddLengthSubarrays(arr)<<endl;

  return 0; 
}
58

အားလုံးထူးဆန်းအရှည် Subarrays Leetcode ဖြေရှင်းချက်၏ပေါင်းလဒ်အတွက်ရှုပ်ထွေးဆန်းစစ်ခြင်း

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

အို (^ ^ ၂) ကွင်းဆက်တစ်ခုစီကိုအောက်ပါအတိုင်းလည်ပတ်နေသော nested ပုံစံဖြင့် loops သုံးခုကိုအသုံးပြုခဲ့သည်။
ပထမ ဦး ဆုံးကွင်းဆက် n / 2 ကြိမ်အပြေးနေသည်။
ဒုတိယကွင်းဆက်လည်ပတ်နေသည် (n-Len) ကြိမ်, ဘယ်မှာ Len 1,3,4 ဖြစ်ပါတယ်။
တတိယကွင်းဆက်မှာအလုပ်လုပ်နေ Len ကြိမ်။
စုစုပေါင်းအချိန်သည် (n / 2) * (n-Len)*Len။ ထို့ကြောင့်အချိန်ရှုပ်ထွေးမှု၏အထက်ဘောင်းသည်အို (n ^ 3) ဖြစ်လိမ့်မည်။ n သည်ပေးထားသောခင်းကျင်း၏အရွယ်အစားဖြစ်သည်။

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

အို (၁) Space ရှုပ်ထွေးစဉ်ဆက်မပြတ်ဖြစ်ပါတယ်။

ချဉ်းကပ်မှု (အချိန်အကောင်းဆုံး)

ကျွန်ုပ်တို့တွေ့ရသည့်အတိုင်းအထက်ပါ brute force solution သည် O (n ^ 3) အချိန်ရှုပ်ထွေးမှုရှိသည်။ ဤအရာကိုကျွန်ုပ်တို့ minimize လုပ်နိုင်သည်။ အထက်ပါချဉ်းကပ်မှုတွင်ကျွန်ုပ်တို့သည် subarrays အမျိုးမျိုးအတွက်တူညီသော element ထပ်ခါထပ်ခါပေါင်းထည့်ခြင်းကြောင့်ဖြစ်သည်။ အကယ်၍ တစ်စုံတစ်ရာသည်ထပ်မံထည့်သွင်းထားခြင်းသို့မဟုတ်စုစုပေါင်းပေါင်းလဒ်ကိုမည်မျှအကြိမ်မည်မျှထည့်သွင်းသင့်ကြောင်းတစ်နည်းနည်းဖြင့်သိရှိလျှင် O (n ^ 3) မှ O (n) သို့အချိန်ရှုပ်ထွေးမှုကိုလျှော့ချနိုင်သည်။

subarrays အားလုံး (even and odd length) ကိုယူမယ်ဆိုရင်၊ အဲ့ဒီကိစ္စမှာ index မှာ element တစ်ခုသည် i သည်စတင်ခြင်းအညွှန်းသည် i နှင့်ညီမျှသည်ထက်နိဂုံးချုပ်ပြီး i သည် index ထက် ပို၍ ကြီးသည်။ ။

ထို့ကြောင့် arr [i] (0-index) ပါဝင်သော subarrays များ၏စုစုပေါင်းသည် (i + 1) * (ni) နှင့်ညီမျှလိမ့်မည်ဟုကျွန်ုပ်တို့ပြောနိုင်သည်။
ဒီတန်ဖိုးက x ဖြစ်ရအောင်။
၄ င်းတို့အနက် (x + 1) / 2 ထူးဆန်းသောအရှည် subarrays များ [arr] ပါရှိသည်။
ထို့အပြင် arr / i ပါ ၀ င်သည့်အလျားလိုက် subarrays ပင် x / 2 သည်။
ထို့ကြောင့် [i] သည်ကျွန်ုပ်တို့၏ဖြေရှင်းချက်အတွက်စုစုပေါင်းပေါင်းလဒ်အတွက် (x + 1) / ၂ ဆအထောက်အကူပြုလိမ့်မည်။

ဤအရာကိုရိုးရှင်းသောဥပမာဖြင့်ကြည့်နိုင်သည်။

arr = [၁၊ ၂၊ ၃၊ ၄၊ ၅] ကိုရေးပါ။

အားလုံးထူးဆန်းအရှည် Subarrays Leetcode ဖြေရှင်းချက်၏ပေါင်းလဒ်

ထို့ကြောင့်တစ်ခုချင်းစီကိုဒြပ်စင် arr ၏ [အလှူငွေ] ထူးဆန်း subarrays = arr [i] * ((i + 1) * (ni) +1) / 2 ။
၎င်းကိုကွင်းဆက်တစ်ခုတည်းဖြင့်ပြုလုပ်နိုင်ပြီးထိုအချိန်တွင်ဤဖြေရှင်းချက်၏ရှုပ်ထွေးမှုသည် linear ဖြစ်လိမ့်မည်။

အားလုံးထူးဆန်းအရှည် Subarrays Leetcode ဖြေရှင်းချက်၏ Sum ၏အကောင်အထည်ဖော်မှု

C ++ အစီအစဉ်

#include <bits/stdc++.h>
using namespace std;

int sumOddLengthSubarrays(vector<int>& arr) 
{
    int sum=0;
    int n=arr.size();

    for(int i=0;i<n;i++)
    {
        int contribution= ((i+1)*(n-i) +1)/2;
        sum+= contribution* arr[i];
    }

    return sum;
}

int main() 
{
    vector<int> arr = {1,4,2,5,3};
  
  cout<<sumOddLengthSubarrays(arr)<<endl;

  return 0; 
}
58

Java အစီအစဉ်

#include <bits/stdc++.h>
using namespace std;

int sumOddLengthSubarrays(vector<int>& arr) 
{
    int sum=0;
    int n=arr.size();

    for(int i=0;i<n;i++)
    {
        int contribution= ((i+1)*(n-i) +1)/2;
        sum+= contribution* arr[i];
    }

    return sum;
}

int main() 
{
    vector<int> arr = {1,4,2,5,3};
  
  cout<<sumOddLengthSubarrays(arr)<<endl;

  return 0; 
}
58

အားလုံးထူးဆန်းအရှည် Subarrays Leetcode ဖြေရှင်းချက်၏ပေါင်းလဒ်အတွက်ရှုပ်ထွေးဆန်းစစ်ခြင်း

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

အို ()) ကျွန်ုပ်တို့သည် array တစ်ခု၏တစ်ခုချင်းစီကိုတစ်ကြိမ်သာဖြတ်သန်းသွားသောအခါအချိန်ရှုပ်ထွေးမှုသည် O (n) ဖြစ်လိမ့်မည်။ n သည်ပေးထားသောခင်းကျင်း၏အရွယ်အစားဖြစ်သည်။

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

အို (၁) ကျွန်ုပ်တို့သည်မည်သည့်အပိုမှတ်ဉာဏ်ကိုမျှအသုံးမပြုပါ။