0s နှင့် 1s တန်းတူအရေအတွက်နှင့်အတူအကြီးဆုံး subarray


ခက်ခဲအဆင့် အလယ်အလတ်
မကြာခဏမေးတယ် အမေဇုံ Coursera GreyOrange ကွမ်းခြံကုန်း မော်ဂန်စတန်လေ Paytm မြတ်နိုး Times ကိုအင်တာနက်
အခင်းအကျင်း hash

သငျသညျကိန်းတစ်ခုခင်းကျင်းပေးထားသည်။ ကိန်းများသည် input array တွင် ၀ နှင့် ၁ ဖြစ်သည်။ ပြstatementနာကကြေငြာချက်သည် 0s နှင့် 1s တန်းတူအရေအတွက်ရှိနိုင်သောအကြီးဆုံး sub-array ကိုရှာဖွေရန်ဖြစ်သည်။

နမူနာ

arr[]={0,1,0,1,0,1,1,1}
0 to 5 (total 6 elements)

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

array နေရာ 0 မှ 5 သည် 0s နှင့် 1s နှင့်ညီမျှသည်မဟုတ်ပါ

0 ရေတွက် 3

1 ရေတွက် ⇒ 3

ပြီးတော့ဒါက 0s နဲ့ 1s တန်းတူတဲ့အကြီးဆုံး sub-ခင်းကျင်းပါ။

0s နှင့် 1s တန်းတူနံပါတ်များနှင့်အတူအကြီးမားဆုံး subarray ကိုရှာဖွေ Algorithm

  1. a) ကြေညာပါ HashMap.
  2. အစုံ ငှေပေါငျး, maxLength, စည်သူလွင် 0 နဲ့ အဆုံးအဖြတ် သို့ -1 ။
  3. Array ကိုဖြတ်ပြီး 1 ၏တန်ဖိုးနှင့်ညီလျှင် element တစ်ခုချင်းစီကို -0 အဖြစ် update လုပ်ပါ။
  4. 0 မှ n-1 အထိ loop ကိုစတင်ပါ (n သည်ခင်းကျင်းခြင်း၏အရှည်ဖြစ်သည်)
    1. arr ၏တန်ဖိုးတစ်ခုချင်းကိုပေါင်းထည့်ပါ။
    2. ပေါင်းလဒ်သည် 0 ဟုတ်မှန်မမှန်စစ်ဆေးပါ။
      1. ထို့နောက်မွမ်းမံပါ maxLength ဈ + 1 အဖြစ်နှင့် အဆုံးအဖြတ် ငါကဲ့သို့
    3. မြေပုံတွင်ပေါင်းလဒ် + n ပါမပါစစ်ဆေးပါ။
      1. ထို့နောက် maxLength ၏အရှည်ကို i - map (sum + n) အနေဖြင့်မြေပုံမှ update လုပ်ပါ။
    4. ကျန်သည်ထို sum + n ကိုမြေပုံထဲထည့်ပါ။
  5. endingIndex ကိုရိုက်ပါ - maxLength + 1 နှင့် endingIndex ။

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

Array ကိုပေးထားပြီး၊ 0s နဲ့ 1s နဲ့ညီမျှတဲ့အကြီးဆုံး sub-array ကိုရှာဖွေဖို့ကျွန်တော်တို့ကိုတောင်းဆိုတယ်။ sub-array ၏ range ကိုရှာပါ။ ၎င်းသည် 0 နှင့် 1s တန်းတူအရေအတွက်ရှိသည့် sub-array အားလုံး၏အရှည်အားလုံးတွင်အကြီးဆုံးဖြစ်သင့်သည်။ ကျနော်တို့ကိုသုံးပါလိမ့်မည် HashMap သိုလှောင်ဘို့ ကိန်း အထဲတွင်တန်ဖိုးများ။ တားဆီးခြင်း ထိရောက်သောချဉ်းကပ်မှုနှင့်ပိုကောင်းသောအချိန်ရှုပ်ထွေးပေးပါသည်။ တန်ဖိုးများကိုယူပါ ငှေပေါငျး, maxLength 0 အဖြစ်ပြီးတော့ကျနော်တို့ကကုဒ်ထဲမှာတစ်ပြိုင်နက်မွမ်းမံသွားနေကြသည်။ ကျနော်တို့မှာ endIndex လို့ခေါ်တဲ့ variable တစ်ခုရှိလိမ့်မယ်။ ဒီအပိုင်းက sub-array အဆုံးသတ်ရဲ့အမြင့်ဆုံးအရှည်ရှိသင့်တဲ့ range ရဲ့နောက်ဆုံးအမှတ်ရဲ့တန်ဖိုးကိုသိမ်းထားလိမ့်မယ်။

Array ကိုဖြတ်ပြီး array ၏တန်ဖိုးတစ်ခုသည် ၀ နှင့်ညီလားဆိုသည်ကိုရှာရန်၊ ၎င်းကိုကျွန်ုပ်တို့သည် -0 အဖြစ်အမှတ်အသားပြုပြီး 1 တွင်ရှိသည့် array တန်ဖိုးထားရှိမည်။ ဘာဖြစ်လို့လဲဆိုတော့ဒီမှာကကျနော်တို့ကအမှန်တကယ်အကွာအဝေးကိုရှာဖွေသွားကြသည်မဟုတ်။ ယုတ္တိဗေဒသည်သုညအမှတ်နှင့်သုညအကြားထပ်ပေါင်းခြင်းကိုရေတွက်ရန်ဖြစ်သည်။ ဒီတော့ 1 ကို -0 အဖြစ်သတ်မှတ်လိမ့်မယ်။ ပြီးတော့ array ထဲကိုတန်ဖိုးတွေကိုထည့်မယ်။ အကယ်၍ ကျွန်တော်တို့ကပေါင်းလဒ်ကို 1 အဖြစ်ရှာလျှင်ဆိုလိုသည်မှာကျွန်ုပ်တို့သည်တူညီသောသုညအပေါင်းတစ်စုံကိုတွေ့ပြီ။ ဘာလို့လဲဆိုတော့ -0 နဲ့ 1 တိုင်း 1 ကိုပေါင်းလဒ်အဖြစ် 0 အဖြစ်ပေါင်းမယ်။ ဒီတော့ငါတို့ရေတွက်နိုင်တယ်။

ကျွန်ုပ်တို့သည် array တစ်ခုအတွင်းရှိတန်ဖိုးတိုင်းကိုစုဆောင်းပြီး 0 နှင့်ညီသည်ဆိုပါကတန်းတူဖြစ်လျှင် maxLength နှင့် arrayI endex ကို update ပြုလုပ်ပါ။ sum + n ကိုမြေပုံထဲသို့ထည့်ပြီး၎င်းတည်ရှိပါကအခြေအနေအချို့ကိုစစ်ဆေးပြီး maxLength နှင့် endingIndex တန်ဖိုးကိုအသစ်ပြောင်းပါ။ endingIndex ကို print ထုတ်ပါ - အကွာအဝေး၏အစမှတ်တစ်ခုအဖြစ် maxLength + 1 နှင့် rangeIndex ကိုအကွာအဝေး၏အစမှတ်ဖြစ်သည်။

0s နှင့် 1s တန်းတူအရေအတွက်နှင့်အတူအကြီးဆုံး subarray

ကုဒ်

0s နှင့် 1s တူညီသောအရေအတွက်နှင့်အတူအကြီးဆုံး subarray ကိုရှာရန် C ++ code

#include<iostream>
#include<unordered_map>

using namespace std;

int getLargestSubA(int arr[], int n)
{
    unordered_map<int, int> MAP;

    int sum = 0;
    int maxLength = 0;
    int endingIndex = -1;

    for (int i = 0; i < n; i++)
        arr[i] = (arr[i] == 0) ? -1 : 1;

    for (int i = 0; i < n; i++)
    {
        sum += arr[i];
        if (sum == 0)
        {
            maxLength = i + 1;
            endingIndex = i;
        }
        if (MAP.find(sum + n) != MAP.end())
        {
            if (maxLength < i - MAP[sum + n])
            {
                maxLength = i - MAP[sum + n];
                endingIndex = i;
            }
        }
        else
            MAP[sum + n] = i;
    }
    cout<<endingIndex - maxLength + 1 <<" to " <<endingIndex;

    return maxLength;
}

int main()
{
    int arr[] = { 0,1,0,1,0,1,1,1 };
    int n = sizeof(arr) / sizeof(arr[0]);

    getLargestSubA(arr, n);
    return 0;
}
0 to 5

0s နှင့် 1s တန်းတူနံပါတ်များဖြင့်အကြီးဆုံးသော subarray ကိုရှာဖွေရန် Java တွင်အကောင်အထည်ဖော်ခြင်း

import java.util.HashMap;

class LargestSubArrayWithEqual01
{
    public static int getLargestSubA(int arr[], int n)
    {
        HashMap<Integer, Integer> MAP = new HashMap<Integer, Integer>();

        int sum = 0;

        int maxLength = 0;
        int endingIndex = -1;

        for (int i = 0; i < n; i++)
        {
            arr[i] = (arr[i] == 0) ? -1 : 1;
        }

        for (int i = 0; i < n; i++)
        {
            sum += arr[i];
            if (sum == 0)
            {
                maxLength = i + 1;
                endingIndex = i;
            }
            if (MAP.containsKey(sum + n))
            {
                if (maxLength < i - MAP.get(sum + n))
                {
                    maxLength = i - MAP.get(sum + n);
                    endingIndex = i;
                }
            }
            else
                MAP.put(sum + n, i);

        }
        int end = endingIndex - maxLength + 1;
        System.out.println(end + " to " + endingIndex);

        return maxLength;
    }
    
    public static void main(String[] args)
    {
        int arr[] = {0,1,0,1,0,1,1,1};
        int n = arr.length;

        getLargestSubA(arr, n);
    }
}
0 to 5

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

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

အို (ဎ) ဘယ်မှာ “ n” သည် array ထဲရှိ element အရေအတွက်ဖြစ်သည်။ ဤတွင်ကျွန်ုပ်တို့သည် HashMap ကိုအသုံးပြုသောကြောင့် O (n) တွင်ဤပြproblemနာကိုဖြေရှင်းနိုင်သည်။ အဘယ်ကြောင့်ဆိုသော် HashMap သည် O (1) အချိန်ရှုပ်ထွေးမှုတွင် element များကိုထည့်ခြင်း၊ ဖျက်ခြင်းသို့မဟုတ်ပြုပြင်ခြင်းလုပ်နိုင်သောကြောင့်ဖြစ်သည်။

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

အို (ဎ) ဘယ်မှာ “ n” သည် array ထဲရှိ element အရေအတွက်ဖြစ်သည်။ အဆိုးဆုံးအမှု၌ hashmap သို့ထည့်သွင်းမည့် element အရေအတွက်သည်အများဆုံးဖြစ်သည်။ ဤသည် linear အာကာသရှုပ်ထွေးအောင်မြင်သည်။