Equal Sum Leetcode Solution ဖြင့်အပိုင်းသုံးပိုင်းခွဲထုတ်ပါ


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

အဆိုပါပြproblemနာ partition ကို အခင်းအကျင်း Equal Sum နှင့်အတူအပိုင်းသုံးပိုင်းသို့ Leetcode Solution သည်ကျွန်ုပ်တို့အားခင်းကျင်းပြသမှုသို့မဟုတ်အားနည်းချက်ကို ပေး၍ အစီအစဉ်၏အခန်းကန့် ၃ ခုရှိမရှိရှိမရှိမေးမြန်းသည်။ ဒီနေရာတွင် partition အားဖြင့်ဆိုလိုသည်မှာ i, j နှစ်ခုရှိကြောင်း၊ ဆိုလိုသည်မှာ start မှ i သို့အညွှန်း element များ၏ပေါင်းလဒ်သည် i + 1 မှ jth index သို့ element များ၏ပေါင်းလဒ်နှင့်ညီသည်။ ပြီးတော့ j + 1 index ကနေနောက်ဆုံး element တွေအထိပေါင်းလဒ်က array ရဲ့ပထမ segments နှစ်ခုနဲ့လည်းညီတယ်။ အကယ်၍ ထိုကဲ့သို့သောညွှန်းကိန်းနှစ်ခုရှိပါကခင်းကျင်းမှုကိုတူညီသောပေါင်းလဒ်ဖြင့်သုံးပိုင်း ခွဲ၍ ရနိုင်သည်။ ဒီဖြေရှင်းချက်ထဲကိုမ ၀ င်ခင်ဥပမာအနည်းငယ်ကြည့်ရအောင်။

Equal Sum Leetcode Solution ဖြင့်အပိုင်းသုံးပိုင်းခွဲထုတ်ပါ

arr = [0,2,1,-6,6,-7,9,1,2,0,1]
true

ရှင်းလင်းချက်။ ။ ခင်းကျင်းမှုအားတန်းတူပေါင်းလဒ်သုံးခုအဖြစ် ခွဲ၍ ရသောကြောင့်။ ထို့ကြောင့်ကျွန်ုပ်တို့သည် array ကိုညီမျှသောပမာဏသုံးခုအဖြစ်ပိုင်းခြားနိုင်သည်။ ပိုပြီးတရားဝင်, 0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1 ။

arr = [0,2,1,-6,6,7,9,-1,2,0,1]
false

ရှင်းလင်းချက် - ခင်းကျင်းမှုတစ်ခုတည်းကိုပဲသီးခြားကဏ္ three သုံးခုခွဲခြားရန်နည်းလမ်းမရှိသောကြောင့်။ ထို့ကြောင့်အဖြေမှားသည်။

တူညီသော Sum Leetcode ဖြေရှင်းနည်းသုံးခုခွဲခြင်း Array အတွက်ချဉ်းကပ်မှု

ပြproblemနာက Partition Array ကို Equal Sum နဲ့ Leftcode Solution သုံးပိုင်းခွဲခြားထားတယ်။ ကျွန်တော်တို့ကပေးထားတဲ့ Array ကိုတူညီတဲ့ပမာဏတွေရှိတဲ့ disjoint subarrays သုံးခုခွဲလို့ရမလားလို့မေးတယ်။ ဒီတော့ဒီပြsolveနာကိုအရင်ဖြေရှင်းဖို့၊ စုစုပေါင်း array ကိုရှာရမယ်။ စုစုပေါင်းပေါင်းလဒ်ကို 3 နဲ့စားလို့မရဘူးဆိုရင်တော့အဖြေကမှားနေတယ်။ ဘာဖြစ်လို့လဲဆိုတော့ဒါက array ကိုတူညီတဲ့အပိုင်းခွဲတွေခွဲဖို့နည်းလမ်းမရှိတော့လို့ပဲ။ ဒါပေမယ့်ဒီပေါင်းလဒ်ကို ၃ နဲ့စားလို့ရတယ်ဆိုလျှင် sum / 3 ရနိုင်မလားဆိုတာကိုစစ်ဆေးလိမ့်မယ်။ ကျွန်ုပ်တို့သည်စုစုပေါင်းပေါင်းလဒ် / ၃ နှင့်ညီသည်ကိုမတွေ့မချင်းထိုစဉ်ဆက်မပြတ်ပေါင်းလဒ်ကိုသိုလှောင်ခြင်းဖြင့်ဤလုပ်ငန်းစဉ်ကိုကျွန်ုပ်တို့တုပကြသည်။ အကယ်၍ ကျွန်ုပ်တို့သည်စုစုပေါင်းကိုလက်ရှိ element = sum / 3 အထိရောက်လျှင်၊ စုစုပေါင်းသုညသို့ပြန်သွားသည်။ ထပ်၍ ထပ်၍၊ စုစုပေါင်းဒြပ်စင် = sum / 3 ကိုရှာပါ။ ငါတို့ကဒီနည်းအားဖြင့်ပေါင်းလဒ် / 3 0 ကြိမ်ရနိုင်လျှင်။ ကျွန်ုပ်တို့သည် array ကိုအခြားအပိုင်းသုံးပိုင်း ခွဲ၍ ခွဲနိုင်သည်ကိုအာမခံနိုင်သည်။

ကုဒ်

တူညီသော Sum Leetcode Solution နှင့်အပိုင်းသုံးခု ခွဲ၍ Partition Array အတွက် C ++ code

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

bool canThreePartsEqualSum(vector<int>& arr) {
    int sum = 0;
    for(int i=0;i<arr.size();i++)
        sum += arr[i];
    if(sum % 3 != 0)
        return false;
    int sum3 = sum/3, partitions = 0;
    sum = 0;
    for(int i=0;i<arr.size();i++){
        sum += arr[i];
        if(sum == sum3){
            ++partitions;
            sum = 0;
        }
    }
    return partitions >= 3;
}

int main() {
  vector<int> arr({0,2,1,-6,6,-7,9,1,2,0,1}); 
  cout<<canThreePartsEqualSum(arr);
  return 0;
}
true

Partition Array အတွက် Java code ကို Equal Sum Leetcode Solution ဖြင့်အပိုင်းသုံးပိုင်းခွဲပါ

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main
{
  public static boolean canThreePartsEqualSum(int[] arr) {
        int sum = 0;
        for(int i=0;i<arr.length;i++)
            sum += arr[i];
        if(sum % 3 != 0)
            return false;
        int sum3 = sum/3, partitions = 0;
        sum = 0;
        for(int i=0;i<arr.length;i++){
            sum += arr[i];
            if(sum == sum3){
                ++partitions;
                sum = 0;
            }
        }
        return partitions >= 3;
    }
 
  public static void main (String[] args) throws java.lang.Exception{
    int[] arr = {0,2,1,-6,6,-7,9,1,2,0,1};
 
    System.out.print(canThreePartsEqualSum(arr));
  }
}
true

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

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

အို (N)၊ ကျနော်တို့ခင်းကျင်းနှစ်ကြိမ်ဖြတ်သန်းကြသော်လည်း။ သို့သော်၎င်းကို linear အချိန်ရှုပ်ထွေးမှုအဖြစ်မှတ်ယူနိုင်သည်။ အဘယ်ကြောင့်ဆိုသော်ခင်းကျင်းသွားသောအချိန်သည်၎င်း၏အရွယ်အစားပေါ်တွင်မူမတည်သောကြောင့်ဖြစ်သည်။

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

အို (၁)၊ ကျနော်တို့ဒြပ်စင်တစ်ခုစဉ်ဆက်မပြတ်အရေအတွက်ကိုအသုံးပြု။ အသီးအသီးအညွှန်းကိန်းနှင့်ပတ်သက်။ အချို့သောတိကျသောသတင်းအချက်အလက်သိုလှောင်ဘူးကတည်းက။ အဆိုပါအာကာသရှုပ်ထွေးစဉ်ဆက်မပြတ်ဖြစ်ပါတယ်။