متواضع سرنی لیټکوډ


مشکل کچه منځني
په مکرر ډول دننه پوښتل کیږي ترلاسه کړئ Amazon فیسبوک د ګوګل
پیشه ځورول

ستونزه بیان

د "دوام لرونکي اری لیټکوډ" ستونزه وايي چې تاسو ته ورکړل شوي سور د [a] د اندازې n یوازې د 1 او 0's څخه جوړ دی. ومومئ ترټولو اوږد فرعي په کوم کې چې د 1's شمیره د 0's شمیر سره مساوي وي.

بېلګه

متواضع سرنی لیټکوډ

a[ ] = {1, 0, 1, 1, 1, 0, 0}
1 to 6

توضیحي: له 1 څخه تر 6 شاخص پورې د فرعي غوره کول موږ د اوږدوالي 6 غوره پایله درکوي. د 1 څخه تر 6 شاخص پورې متناسب سرسري دری صفرونه او 3 لري. دلته موږ د 3 پر اساس شاخصونه په پام کې نیولي دي.

a[ ] = {1, 1}
No such subarray

او کړنلاره

د بې لارې طریقه

ټولې احتمالي فرعي ډکې رامینځته کړئ. وګورئ چې کوم کوم فرعي شتون شتون لري په کوم کې چې د 1's شمیره د 0's شمیر سره مساوي وي. موږ د subarray کی left کی right او ​​ښیې پولې لپاره دوه نښې I او j کاروو. بیا موږ ګورو چې د i څخه j ته د subarray مجموعه = 0 لري ، وروسته د 0--1 سره ځای په ځای کول. که دا ریښتیا وي ، موږ د شرایطو پوره کولو لپاره فرعي زیرمه موندلې ده. اوس موږ خپل ځواب تازه کوو.

د دوامداره سرې لیټکوډ ستونزې لپاره الګوریتم

1. Initialize a binary array a[] of size n and three variables sum, max=-1, and start.
2. Traverse through the array and update sum as -1 if a[i] is 0 else 1.
3. Traverse the inner loop and add -1 in sum if a[i] is 0 else 1.
4. Check if the sum is 0 and max is less than j-i+1, update max as j-i+1 and start as i.
5. Outside the loops check if max is -1 print "No such subarray" else print starting and ending index.

کوډ

د C ++ برنامه د متناسب سرلیک لیټکوډ ستونزه حل کولو لپاره
#include <bits/stdc++.h> 
using namespace std; 
  
int subArray(int a[], int n){ 
    int sum = 0; 
    int max = -1, start; 
  
    for(int i=0; i<n-1; i++){ 
        sum = (a[i]==0) ? -1 : 1; 
  
        for(int j=i+1; j<n; j++){ 
            (a[j]==0) ? (sum+=-1) : (sum+=1); 
  
            if(sum == 0 && max < j-i+1){ 
                max = j-i+1; 
                start = i; 
            } 
        } 
    } 
    if(max == -1) 
        cout<<"No such subarray"; 
    else
        cout<<start<<" to "<<start+max-1; 
  
    return max; 
} 
  
int main(){ 
    int a[] = { 1, 0, 1, 1, 1, 0, 0 }; 
    int n = sizeof(a) / sizeof(a[0]); 
  
    subArray(a, n); 
    return 0; 
}
1 to 6
د جاوا برنامه د دوام لرونکي سرې لیټکوډ ستونزې حل کولو لپاره
class LongestSubArray{
    int subArray(int a[], int n){ 
        int sum = 0; 
        int max = -1, start=0,end=0; 
        
        for(int i=0; i<n-1; i++){ 
            sum = (a[i]==0) ? -1 : 1; 
            
            for(int j=i+1; j<n; j++){ 
                if(a[j] == 0) 
                    sum += -1; 
                else
                    sum += 1;  
                
                if(sum == 0 && max < j-i+1){ 
                    max = j-i+1; 
                    start = i; 
                } 
            } 
        } 
        if(max == -1) 
            System.out.println("No such subarray");
        else
            end = start+max-1;
            System.out.println(start+" to "+end);
        
        return max; 
    } 
    public static void main(String[] args){ 
        LongestSubArray s = new LongestSubArray(); 
        int a[] = { 1, 0, 1, 1, 1, 0, 0 }; 
        int n = a.length; 
        
        s.subArray(a, n); 
    } 
}
1 to 6

د پیچلتیا تحلیل

د وخت پیچلتیا

له هغه ځایه چې موږ د تیر ټکي ساتلو پرمهال له صف څخه تیروو. موږ د ډیری وخت پیچلتیا ترلاسه کړه  O (N)2) چیرې چې n په ورکړل شوي صف کې د عناصرو شمیر دی a [].

د ځای پیچلتیا

O (1) ځکه چې موږ دوامداره اضافي ځای کارولی. موږ یوازې د متغیرونو دوامداره شمیر رامینځته کړی. مګر د لومړني ان پټ سرپا otherې سربیره هیڅ کوم ارار ونه کارول شو. مګر برنامه په مجموع کې د O (N) ځای پیچلتیا لري ځکه چې موږ د ننوت عناصرو ذخیره کولو لپاره یو صف کارولی.

د هش نقشه کارول

د دوامداره سرې لیټکوډ ستونزې لپاره الګوریتم

1. Initialize a binary array a[] of size n.
2. Initialize an unordered map.
3. Traverse through the array and update the array value of the current index as -1 if current value if 0 else 1.
4. Traverse through the array and add the elements.
5. If the sum is 0, update max as i+1 and end as i.
6. Else Traverse map and update max as i - map(sum+n) and end as i if max is less than i - map(sum+n) else update map(sum+n) as i.
7. Traverse through the array and update the array value of the current index as 0 if current value is -1 else 1.
8. If the end is greater than -1 print starting and ending index.
9. Else print "No such subarray".

هغه څه چې موږ دلته ترسره کړي ، په ساده ډول کله چې موږ اړتیا لرو ترټولو لوی فرعي زیرمې ومومئ. 0 څه چې موږ کوو هغه دا دی چې موږ د پری ماکس اندازه اخلو او زموږ په نقشه کې چیک کوو که چیرې داسې کوم ځای شتون ولري چې موږ ورته رقم ومومئ. بیا فرعي سرچینې چې په نقشه +1 کې زیرمه شوي ارزښت څخه پیل کیږي اوسني شاخص ته 0 دی. دلته ، موږ د کلیدي په توګه (جمع + n) کار کوو. مګر موږ کولی شو دغه رقم مستقیم هم وکاروو. مګر که موږ د کلیدي په توګه (جمع + n) وکاروو نو بیا موږ د هش میپ پرځای صف هم وکاروو. ځکه نو بیا موږ تضمین کولی شو چې (جمع + n)> = 0 او د صف ترتیب کول له 0 څخه پیل کیږي.

کوډ

د C ++ برنامه د متناسب سرلیک لیټکوډ ستونزه حل کولو لپاره
#include <bits/stdc++.h> 
using namespace std; 
  
int subArray(int a[], int n){ 
    
    unordered_map<int, int> hM; 
  
    int sum = 0, max = 0, end = -1; 
  
    for(int i=0; i<n; i++) 
        a[i] = (a[i] == 0) ? -1 : 1; 
  
    for(int i=0; i<n; i++){ 
        sum += a[i]; 
  
        if(sum == 0){ 
            max = i + 1; 
            end = i; 
        } 
  
        if(hM.find(sum + n) != hM.end()){ 
            if(max < i - hM[sum + n]){ 
                max = i - hM[sum + n]; 
                end = i; 
            } 
        } 
        else 
            hM[sum + n] = i; 
    } 
  
    for(int i=0; i<n; i++) 
        a[i] = (a[i] == -1) ? 0 : 1; 
        
    if(end>-1)
        cout<<end - max + 1<<" to "<<end; 
    else
        cout<<"No such subarray";
    return max; 
} 
  
int main(){ 
    int a[] = {1, 0, 1, 1, 1, 0, 0}; 
    int n = sizeof(a) / sizeof(a[0]); 
  
    subArray(a, n); 
    return 0; 
} 
1 to 6
د جاوا برنامه د دوام لرونکي سرې لیټکوډ ستونزې حل کولو لپاره
import java.util.HashMap;

class LongestSubArray{
    int subArray(int a[], int n){ 
        
        HashMap<Integer, Integer> hM = new HashMap<Integer, Integer>(); 
  
        int sum = 0, max = 0, end = -1, start = 0; 
  
        for(int i=0; i<n; i++){ 
            a[i]=(a[i]==0) ? -1 : 1; 
        } 
  
        for(int i=0; i<n; i++){ 
            sum += a[i]; 
  
            if(sum == 0){ 
                max = i + 1; 
                end = i; 
            } 
  
            if(hM.containsKey(sum + n)){ 
                if(max < i - hM.get(sum + n)){ 
                    max = i - hM.get(sum + n); 
                    end = i; 
                } 
            } 
            else 
                hM.put(sum + n, i); 
        } 
  
        for(int i=0; i<n; i++) { 
            a[i] = (a[i] == -1) ? 0 : 1; 
        } 
  
        int index = end - max + 1; 
        
        if(end>-1)
            System.out.println(index + " to " + end); 
        else
            System.out.println("No such subarray"); 
        return max;  
    } 
    public static void main(String[] args){ 
        LongestSubArray s = new LongestSubArray(); 
        int a[] = { 1, 0, 1, 1, 1, 0, 0 }; 
        int n = a.length; 
        
        s.subArray(a, n); 
    } 
}
1 to 6

د پیچلتیا تحلیل

د وخت پیچلتیا

O (N) چیرې چې n په ورکړل شوي صف کې د عناصرو شمیر دی a []. له هغه وخته چې ای غیر منظم_ نقشه / هش میپ کارولی ، موږ د O (N) وخت ترلاسه کولو توان درلود ځکه چې هاش میپ O (1) وخت ته اجازه ورکوي چې د ننوتلو لټون ، حذف کولو ترسره کړي.

د ځای پیچلتیا

O (N) ځکه چې موږ د N اضافي ځای کارولی. له هغه وخته چې موږ د هاشیماپ اعلان وکاروه د N عناصرو په اړه معلومات ذخیره کړل ، په خورا خراب حالت کې چې کولی شي N عناصر ولري.