ከ 1 ቶች ብዛት አንድ በጣም የ 0 ኛ ቆጠራ ያለው ረጅሙ ንዑስ ቡድን


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ Accenture አማዞን ዴ ሻው ሳምሰንግ
ሰልፍ ሃሽ

አንድ ሰጥተናል ደርድር የቁጥር ቁጥሮች። አንድ ድርድር የ 1 እና 0 ን ብቻ ይይዛል። የችግሩ መግለጫ ረጅሙን ንዑስ-ድርድር ርዝመቱን ለማወቅ ይጠይቃል ይህም የ 1 አሃዝ ብዛት ያለው በአንድ ንዑስ ድርድር ውስጥ ከ 0 ዎቹ ቁጥር አንድ ብቻ ይበልጣል ፡፡

ለምሳሌ

ግቤት

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

ውጤት

5

ማብራሪያ:

ከ 0 እስከ 4 መረጃ ጠቋሚ ፣ {1, 0, 1, 1, 0} ሶስት ናቸው 1 እና ሁለት 0 ዎቹ. አንድ ብቻ ከ 1 ዎቹ ከ 0 ዎቹ መቁጠር።

ግቤት

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

ውጤት

3

ማብራሪያ:

ከ 0 እስከ 2 መረጃ ጠቋሚ ፣ {1, 0, 1} ፣ ሁለት 1 እና አንድ 0 አሉ ፡፡ አንድ ብቻ ከ 1 ዎቹ ከ 0 ዎቹ መቁጠር።

አልጎሪዝም

  1. ካርታ ያውጅ ፡፡
  2. ድምር እና ውፅዓት ርዝመቱን ወደ 0 ያቀናብሩ።
  3. ድርድሩን ያቋርጡ ፣ i = 0 እስከ i <n።
    1. Arr [i] እውነት ከሆነ ከ 0 ጋር እኩል መሆኑን ያረጋግጡ ከዚያም በድምሩ -1 ይጨምሩ።
    2. ሌላ ለመደመር +1 ያክሉ።
    3. ከሆነ ያረጋግጡ ድምር እኩል ነው ወደ 1 ፣ ከዚያ የውጤት ዋጋውን በ 1 ይጨምሩ።
    4. ሌላ ፣ አንድ ካርታ እውነት ከሆነ ድምር ከሌለው ያረጋግጡ ከዚያም የ i ን ድምር እና የአሁኑን ዋጋ ከድምርው ጋር በካርታው ላይ ያኑሩ።
    5. አንድ ካርታ (ድምር -1) የያዘ መሆኑን ያረጋግጡ ፡፡
    6. የውጤት ርዝመት ከአይ-ኢንዴክስ ያነሰ ከሆነ (በካርታው ውስጥ ያለው ድምር እሴት)።
      1. እውነት ከሆነ ፣ ከዚያ የውጤቱን ርዝመት ወደ አይ-ኢንዴክስ ያዘምኑ።
  4. የውጤት ርዝመት ይመልሱ።

ማስረጃ

እኛ እናሳውቃለን ካርታ. ሁኔታው የሚያረካ ከሆነ በዚያ ካርታ ውስጥ የመደመር ዋጋ እና የአሁኑ የመረጃ ጠቋሚ እሴት እናከማቸዋለን ፡፡ ድርድሩን ስናቋርጥ ሁለት ተለዋዋጮችን ወስደህ ድምርን 0 እና ውፅዓት ርዝመት እስከ 0. ድረስ አስቀምጥ ፣ እያንዳንዱን የአንድ ድርድር አባል እንመርጣለን ፣ እና አሪ [i] ከ 0 ጋር እኩል መሆኑን እናረጋግጣለን ፣ እኩል ሆኖ ከተገኘ እንጨምራለን -1 ለመደመር እና ለመደመር ለማከማቸት ፣ ካልሆነ 0 መሆን ካላገኘን አዎንታዊውን 1 ለመደመር በመደመር እንጨምረዋለን ፡፡

ከዚያ አሉታዊ 1 እና አዎንታዊ 1 በስተጀርባ ያለው ምክንያት ፣ ሁሉንም 0 ቶች ወደ -1 በማስመሰል ከ 1 ጋር አክለናል ፣ ስለሆነም ሁልጊዜ 0 ን እናገኛለን ፡፡ ግን እኛ አዎንታዊ 1 ን በድምፅ እንመረምራለን ፣ ይህም አንድ ተጨማሪ 1 እና ከዚያ የ 0 ዎቹ ብዛት እንደሚኖረን ያሳያል ፡፡

እንበል ፣ 1 ለ -0 የማስመሰል ከሆነ 1 ፣ 0 ፣ 1 እንወስዳለን ፣ ያንን 0 በመጀመሪያዎቹ 2 ቁጥሮች እናገኛለን ፣ በሶስተኛው ቁጥር ደግሞ ሁኔታችን የተሟላ መሆኑን እናገኛለን ፡፡ የ 1 እና የ 0 ንዑስ ድርድር አገኘን ከአንድ ተጨማሪ ከ 1 ከ 0. በላይ ቆጠራን ያለንበትን ሁኔታ እናርካለን ፡፡ ለዚያም ነው በሚቀጥለው ሂሳብ (ሂሳብ) ቀመር ድምር ከ 1 ጋር እኩል ከሆነ እና የውጤቱን ርዝመት የሚያሻሽለው የምንፈልገው። በመጨረሻው መግለጫው አዲሱን የውጤት ርዝመት ካገኘን የቀደመውን አሁን ባለው የውጤት ርዝመት ማዘመን ያስፈልገናል እናም የውጤቱን ርዝመት እንመልሳለን ፡፡

አፈጻጸም

የ Cs + መርሃግብር ለ ረጅሙ ንዑስ ቡድን የ 1 ቶች ብዛት ከ 0 ዎቹ ብዛት ይበልጣል

#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

የ 1 ኛ እና የ 0 ቶች ቁጥርን የሚጨምር የጃቫ ፕሮግራም ለ ረዥሙ ንዑስ ቡድን

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

ውስብስብነት ያለው ትንተና ረዘም ላለ ንዑስ ቡድን የ 1 ቶች ብዛት ከ 0 ቶች ብዛት ይ Countል

የጊዜ ውስብስብነት

ሆይ (n) የት “N”  በድርድሩ ውስጥ ያሉት ንጥረ ነገሮች ብዛት ነው።

የቦታ ውስብስብነት

ሆይ (n) የት “N”  በድርድሩ ውስጥ ያሉት ንጥረ ነገሮች ብዛት ነው።