ተጣማጅ ድርድር  


የችግር ደረጃ መካከለኛ
ውስጥ በተደጋጋሚ ተጠየቀ አማዞን MakeMyTrip ሞርጋን ስታንሊ Paytm
ሃምሽንግ የተንሸራታች መስኮት

ተሰጥቷል አንድ ደርድር ቁጥሮችን 0 እና 1 ብቻ ያካተተ ፡፡ ኦ እና 1 ዎችን በእኩል የሚያካትት ረጅሙ ተጓዳኝ ንዑስ ድርድር ርዝመት መፈለግ አለብን ፡፡

ለምሳሌ  

ግቤት

arr = [0,1,0,1,0,0,1]

ዉጤት

6

ማስረጃ

በጣም ረጅሙ ተያያዥነት ያለው ንዑስ ድርድር በቀይ ምልክት ተደርጎበታል [0,1,0,1,0,0,1] እና ርዝመቱ 6 ነው።

አልጎሪዝም  

  1. የ maxlen ዋጋን ወደ 0 ያቀናብሩ።
  2. በመጀመሪያ ቀለበቱ ውስጥ zer_count ወደ 0 ፣ one_count to 0 ፣ ሁለት ቀለበቶችን ይጠቀሙ ፡፡
  3. ከሆነ የ በአንድ የተወሰነ መረጃ ጠቋሚ ላይ ድርድር ተገኝቷል 0 ከዚያም የዜሮ_ቁጥርን በ 1 ይጨምሩ።
  4. ሌላ ማዘመን እና አንድ_ቁጥር በ 1 ይጨምሩ።
  5. በእያንዳንዱ ድግግሞሽ ላይ ዜሮ_ቁጥር ከአንድ_ቁጥር ጋር እኩል ከሆነ ፣ እኩል ከሆነ ፣ ከዚያ መካከል ትልቁን ቁጥር ይፈልጉ (maxlen እና j-i + 1)
  6. መመለስ maxlen

ማስረጃ  

ዋናው ሃሳባችን ዜሮ የሆነ እና አንድ ብቻ ያለው ረጅሙ ተጓዳኝ ንዑስ ቡድንን መፈለግ ነው ፣ ስለሆነም ዋና ትኩረታችን ያንን ርዝመት መፈለግ ነው ፡፡

ስለሆነም ጎጆን ለሉፕ እንጠቀማለን ፡፡ በውጭ ዑደት ውስጥ የዜሮ_ቁጥር እና የአንድ_ቁጥር እሴት 0 ን እንጀምራለን ፣ ምክንያቱም ከእያንዳንዱ ተደጋጋሚነት በኋላ ከውስጣዊው ዑደት ሲወጣ ሁሉንም እንደገና ለማጣራት የዜሮ_ቁጥር እና አንድ_ካውንት አዲስ እሴቶች ያስፈልጉናል። የድርድሩ ርዝመት እስከሚደርስ ድረስ በሉፉው ላይ እናስተላልፋለን ፡፡

ተመልከት
በተሰጠው ክልል ዙሪያ የአንድ ድርድር ሶስት መንገድ ክፍፍል

አሁን እያንዳንዱን የድርድር ዋጋ ይፈትሻል ፣ arr [ማውጫ] ከ 0 ጋር እኩል ዋጋ ካለው 1 ወይም 0 እሴት ካለው ከዚያ የዜሮ_ካውንትን ዋጋ በ 1 ያሻሽሉ እና የአር [ኢንዴክስ] እሴት ካለ 1 ሆኖ ተገኝቷል ፣ ከዚያ የአንድ_ቁጥር ዋጋን በ 1 ያሻሽላል እና ይጨምራል።

አሁን ፣ ቀጣዩ ከሆነ ፣ ዜሮ_ካውንቱ ከአንድ_ቁጥር ጋር እኩል መሆኑን ያረጋግጡ ፣ እኩል ከሆነ ፣ ከዚያ በ maxlen እና j-i + 1 መካከል ትልቁን ቁጥር ይወቁ እና ትልቁን ቁጥር በ maxlen ውስጥ ያከማቻሉ።

ለምሳሌ

ድርድር ተሰጠ እንበል: arr [] = {1,0,0,1,0,1,0}

ዜሮ_ቁጥር = 0 ፣ one_count = 0 ፣ maxlen = 0

በ i = 0, => j = i

j = 0

በአር [j] ከ 0 ጋር እኩል አይደለም ፣ ከዚያ አንድ_ቁጥር ++ ፣ አንድ_ቁጥር = 1 ማለት ነው

j = 1

በአር [j] ከ 0 ጋር እኩል ነው ፣ ከዚያ ዜሮ_ቁጥር ++ ፣ ዜሮ_ቁጥር = 1 ማለት ነው

ማገጃው ከተፈፀመ በሚቀጥለው በዚህ ቦታ በ maxlen እና በ j-i + 1 መካከል ትልቅ አይሰጥም እና በ maxlen ውስጥ 2 ን ይመልሳል ፡፡

j = 2

በአር [j] ከ 0 ጋር እኩል ነው ፣ ከዚያ ዜሮ_ቁጥር ++ ፣ ዜሮ_ቁጥር = 2 ማለት ነው

j = 3

በአር [j] ከ 0 ጋር እኩል አይደለም ፣ ከዚያ አንድ_ቁጥር ++ ፣ አንድ_ቁጥር = 2 ማለት ነው

ማገጃው ከተፈፀመ በሚቀጥለው በዚህ ቦታ በ maxlen እና j-i + 1 መካከል ትልቅ አይሰጥም እና በ maxlen ውስጥ 4 ን ይመልሳል ፡፡

j = 4

በአር [j] ከ 0 ጋር እኩል ነው ፣ ከዚያ ዜሮ_ቁጥር ++ ፣ ዜሮ_ቁጥር = 3 ማለት ነው

j = 5

በአር [j] ከ 0 ጋር እኩል አይደለም ፣ ከዚያ አንድ_ቁጥር ++ ፣ አንድ_ቁጥር = 3 ማለት ነው

ማገጃው ከተፈፀመ በሚቀጥለው በዚህ ቦታ በ maxlen እና j-i + 1 መካከል ትልቅ አይሰጥም እና በ maxlen ውስጥ 6 ን ይመልሳል ፡፡

j = 6

በአር [j] ከ 0 ጋር እኩል ነው ፣ ከዚያ ዜሮ_ቁጥር ++ ፣ ዜሮ_ቁጥር = 4 ማለት ነው

እና ሁሉም ሁኔታዎች እስኪያጡ ድረስ እስከመጨረሻው ቀለበቱን እንደገና ማሠራቱን ይቀጥላል።

እና maxlen ን እንደ 6 ይመልሱ።

አፈጻጸም  

ለ “Contiguous Array” C ++ ፕሮግራም

#include <iostream>
using namespace std;
int contiguous_Array(int arr[], int n)
{
    int i,j,maxlen=0;
    for( i = 0 ; i < n ; i++)
    {
        int zero_count=0,one_count=0;
        for(j = i ; j < n ; j++)
        {
            if( arr[j] == 0 )
            {
                zero_count++;
            }
            else
            {
                one_count++;
            }
            if(zero_count==one_count)
            {
                maxlen=std::max(maxlen,j-i+1);
            }
        }
    }
    return maxlen;
}
int main()
{
    int arr[]= {1,0,0,1,0,1,0};
    int n=sizeof(arr)/sizeof(arr[0]);
    cout <<contiguous_Array(arr,n)<< endl;
    return 0;
}
6

የጃቫ ፕሮግራም ለተጎጂ ድርድር

public class Contiguous_Array {

  public static int solution(int[] arr) {

    int maxlen = 0;

    for (int i = 0; i<arr.length; i++) {

      int zero_count = 0, one_count = 0;

      for (int j = i; j<arr.length; j++) {

        if (arr[j] == 0) {
          zero_count++;
        } else {
          one_count++;
        }
        if (zero_count == one_count) {

          maxlen = Math.max(maxlen, j - i + 1);

        }
      }
    }
    return maxlen;
  }
  public static void main(String args[]) {

    int[] arr = new int[] {
      0, 1, 0, 1, 0, 0, 1
    };

    System.out.println(solution(arr));

  }
}
6

ለተዛማጅ ድርድር ውስብስብነት ትንተና  

የጊዜ ውስብስብነት

ኦ (N * N) የት N የተሰጠው ድርድር መጠን ነው።

ተመልከት
ቀለሞችን ደርድር

የቦታ ውስብስብነት

ኦ (1) ምክንያቱም እዚህ ምንም ተጨማሪ ቦታ አንጠቀምም ፡፡

ማጣቀሻ