1s ၏အရေအတွက်ကိုရေတွက်ခြင်းဖြင့်အများဆုံးအရှည်ဆုံး Subarray သည် 0 ၏ Count ထက်ပိုသည်


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

ငါတို့ပေးထားတယ် အခင်းအကျင်း ကိန်း၏။ Array တစ်ခုမှာ 1 နဲ့ 0 ရမယ်။ ပြstatementနာဖော်ပြချက်သည် 1 ၏ဂဏန်းအရေအတွက်ရှိခြင်းသည် Sub-Array တွင် 0 ၏အရေအတွက်ထက်တစ်ဆပိုသောအရှည်ဆုံး Sub-Array ၏အရှည်ကိုရှာဖွေရန်ဖြစ်သည်။

နမူနာ

input:

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

output:

5

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

0 မှ 4 အညွှန်းကိန်း, {1, 0, 1, 1, 0}, သုံးရှိပါတယ် 1 နဲ့နှစ်ခု 0 ရဲ့။ ၁ ထပ်ကိန်းကသုညထက်ပိုပြီးများတယ်။

input:

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

output:

3

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

0 မှ 2 အညွှန်းကိန်း, {1, 0, 1}, နှစ်ခုနှစ်ခုနှင့်တစ် 1 ကိန်းတွေ။ ၁ ထပ်ကိန်းကသုညထက်ပိုပြီးများတယ်။

algorithm

  1. မြေပုံကိုကြေညာပါ။
  2. ပေါင်းလဒ်နှင့် outputLength 0 င်သတ်မှတ်မည်။
  3. ဈ = 0 မှ i <n နေစဉ်, ခင်းကျင်းဖြတ်သန်း။
    1. arr [i] သည် 0 ဟုတ်မှန်လျှင်မှန်လျှင်မှန်လျှင် -1 ကိုပေါင်းထည့်ပါ။
    2. ကျန်တဲ့ပေါင်းလဒ်က +1 ထည့်ပါ။
    3. ဟုတ်လားစစ်ဆေးပါ ပေါင်းလဒ်သည်ညီမျှသည် 1 သို့ဖြစ်လျှင် outputLength ၏တန်ဖိုးကို 1 တိုးပါ။
    4. အခြားတစ်ခုအနေနှင့်မြေပုံတွင်ပေါင်းလဒ်မပါရှိမရှိစစ်ဆေးပါမှန်လျှင် i ၏ပေါင်းလဒ်နှင့်လက်ရှိတန်ဖိုးကိုပေါင်းခြင်းနှင့်အတူမြေပုံတွင်ထည့်ပါ။
    5. မြေပုံတွင် (sum-1) ပါမပါစစ်ဆေးပါ။
    6. outputLength i-index (မြေပုံထဲမှာပေါင်းလဒ်ရဲ့တန်ဖိုး) ထက်လျော့နည်းသည်ဆိုပါက။
      1. မှန်လျှင်, i-index ကို outputLength ကို update လုပ်ပါ။
  4. output အရှည်ပြန်သွားပါ။

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

ကျနော်တို့ကကြေညာပါလိမ့်မယ် မြေပုံ။ အဲဒီမြေပုံထဲမှာ၊ အခြေအနေကကျေနပ်မယ်ဆိုရင် sum ရဲ့တန်ဖိုးနဲ့အညွှန်းကိန်းတစ်ခုရဲ့လက်ရှိတန်ဖိုးတွေကိုသိမ်းထားလိမ့်မယ်။ variable နှစ်ခုကိုယူပြီး sum ကို 0 နှင့် outputLength သို့ထားရမည်။ array ကိုဖြတ်သန်းသောအခါ element တစ်ခုချင်းစီကိုကျွန်ုပ်တို့ရွေးလိမ့်မည်။ arr [i] သည် 0 နှင့်ညီမျှသည်ကိုစစ်ဆေးမည်၊ -0 to sum ကိုပေါင်းပြီးသိုလှောင်ရမယ်။ မဟုတ်ရင် 1 ဆိုတာမရှိဘူးဆိုရင် 0 ကိုပေါင်းမယ်။ ပေါင်းမယ်။ ပေါင်းမယ်။

ဒီအနုတ် 1 နဲ့အပေါင်း 1 ရဲ့နောက်ကွယ်အကြောင်းပြချက်က 0 မှအားလုံးကိုဟန်ဆောင်ပြီးသူတို့ကို 1 နှင့်ပေါင်းခြင်းကြောင့် 1 ကိုအစဉ်ရလိမ့်မည်။ ဒါပေမယ့်ကျွန်တော်တို့ကအပေါင်း ၁ ကိုရှာမယ်။ အဲဒါက ၁ နဲ့ ၁ ကိုထပ်ပေါင်းမယ်။

ဆိုပါစို့။ ကျွန်ုပ်တို့သည် 1၊ 0 အဖြစ်ဟန်ဆောင်နေပါက ၁၊ ၀၊ ၁ ကိုယူမည်။ 1 ကိုပထမနံပါတ် ၂ ဖြင့်ရလိမ့်မည်။ တတိယနံပါတ်နှင့်ကျွန်ုပ်တို့၏အခြေအနေသည်ပြည့်စုံကြောင်းတွေ့ရှိနိုင်သည်။ ကျွန်တော်တို့မှာ 0 နဲ့ 1 ထပ်ကိန်း ၁ နဲ့ 0 ထပ်ကိန်းတစ်ခုရတယ်။ ကျွန်တော်တို့ရဲ့အခြေအနေကိုကျေနပ်တယ်။ ထို့ကြောင့်၎င်းသည်စုစုပေါင်း algorithm ၏နောက်တစ်ဆင့်တွင်ညီမျှသောပမာဏနှင့် outputLength အရှည်ကို update လုပ်လိမ့်မည်ဆိုပါကကျွန်ုပ်တို့ရှာဖွေလိမ့်မည်။ နောက်ဆုံးအနေဖြင့်၊ အကယ်၍ ကြေညာချက်သည် အကယ်၍ ကျွန်ုပ်တို့သည် output အသစ်အရှည်အသစ်ကိုရရှိပါက၊ ကျွန်ုပ်တို့သည်ယခင် outputLength ဖြင့်ယခင်တစ်ခုအားအသစ်ပြောင်းရန်လိုအပ်ပြီး outputLength ကိုပြန်လာပါမည်။

အကောင်အထည်ဖော်ရေး

အရှည်ဆုံးရေငုပ်သင်္ဘောအတွက် C ++ ပရိုဂရမ်သည်ဂဏန်းအရေအတွက် ၁ ခုထက် ပို၍ တစ်ခုရှိခြင်း

#include <iostream>
#include<unordered_map>

using namespace std;

int getLongestLen(int arr[], int n)
{
    unordered_map<int, int> MAP;
    int sum = 0, outputLength= 0;

    for (int i = 0; i < n; i++)
    {

        if(arr[i] == 0)
            sum += -1;
        else
            sum += 1;


        if (sum == 1)
        {
            outputLength = i + 1;
        }
        else if (MAP.find(sum) == MAP.end())
        {
            MAP[sum] = i;
        }

        if (MAP.find(sum - 1) != MAP.end())
        {
            if (outputLength < (i - MAP[sum - 1]))
                outputLength = i - MAP[sum - 1];
        }
    }
    return outputLength;
}
int main()
{
    int arr[] = {1,0,1,1,0,0,0};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Length of the longest Sub-Array : "<<getLongestLen(arr, n);
    return 0;
}
Length of the longest Sub-Array : 5

အရှည်ဆုံးရေငုပ်သင်္ဘောအတွက် Java ပရိုဂရမ်သည်ဂဏန်းအရေအတွက် ၁ ခုထက်ပိုပြီးပိုများသော Count of 1s ရှိသည်

import java.util.HashMap;

class longestSubArray01
{
    public static int getLongestLen(int arr[], int n)
    {
        HashMap<Integer, Integer> MAP = new HashMap<Integer,Integer>();
        int sum = 0, outputLength = 0;

        for (int i = 0; i < n; i++)
        {
            if(arr[i] == 0)
                sum += -1;
            else
                sum += 1;

            if (sum == 1)
                outputLength = i + 1;
            else if (!MAP.containsKey(sum))
                MAP. put(sum, i);


            if (MAP.containsKey(sum - 1))
            {
                if (outputLength < (i - MAP.get(sum - 1)))
                    outputLength = i - MAP.get(sum - 1);
            }
        }
        return outputLength;
    }
    public static void main(String[] args)
    {
        int arr[] = {1,0,1,1,0,0,0};
        int n = arr.length;
        System.out.println("Length of the longest Sub-Array : " +getLongestLen(arr, n));
    }
}
Length of the longest Sub-Array : 5

အရှည်ဆုံးရေငုပ်သင်္ဘောအတွက်ရှုပ်ထွေးမှုအားခွဲခြမ်းစိတ်ဖြာခြင်း 1s အရေအတွက်၏ထက်ပိုသောရေတွက်မှုအရတွက်ချက်မှု

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

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

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

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