Շարքային զանգված Leetcode


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Amazon facebook Google
Դասավորություն Հեշինգ

Խնդիրի հայտարարություն

«Շարքային զանգված Leetcode» խնդրում նշվում է, որ ձեզ տրվում է անանուն դասավորություն n չափի a [] բաղկացած է միայն 1-ից և 0-ից: Գտնել ամենաերկար ենթաշղթան որում 1-ի թիվը հավասար է 0-ի թվին:

Օրինակ

Շարքային զանգված Leetcode

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

Բացատրություն. 1-ից 6 ինդեքսից ենթադասի ընտրությունը մեզ տալիս է 6 երկարության լավագույն արդյունքը. 1-ից 6 ինդեքսի հարակից զանգվածն ունի 3 զրո և 3: Այստեղ մենք դիտարկել ենք 0-ի վրա հիմնված ինդեքսավորումը:

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

Մոտեցում

Միամիտ մեթոդ

Ստեղծեք բոլոր հնարավոր ենթածրագրերը: Ստուգեք, արդյոք գոյություն ունի ենթածրագիր, որում 1-ի թիվը հավասար է 0-ի թվին: Ենթանկարի ձախ և աջ սահմանի համար մենք օգտագործում ենք i և j երկու ցուցիչ: Դրանից հետո մենք ստուգում ենք, արդյոք i- ից j ենթահաշվի գումարը ունի sum = 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 ++ ծրագիր ՝ հարակից զանգվածի Leetcode- ի խնդիրը լուծելու համար
#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
Java ծրագրի հարակից զանգված Leetcode- ի խնդիրը լուծելու համար
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

Բարդության վերլուծություն

Timeամանակի բարդություն

Քանի որ այստեղ մենք անցնում էինք զանգվածը, միաժամանակ ցուցիչը ֆիքսված պահելով: Մենք հասանք բազմանդամ ժամանակի բարդության  ՎՐԱ2) որտեղ n- ը տրված զանգվածում տարրերի քանակն է a []:

Տիեզերական բարդություն

Ո (1) քանի որ մենք օգտագործում էինք անընդհատ լրացուցիչ տարածք: Մենք ստեղծեցինք միայն փոփոխականների անընդհատ քանակ: Բայց չօգտագործեց որևէ այլ զանգված, բացի մուտքի սկզբնական զանգվածից: Բայց ծրագիրն, ընդհանուր առմամբ, ունի O (N) տիեզերական բարդություն, քանի որ մուտքի տարրերը պահելու համար մենք զանգված ենք օգտագործել:

Օգտագործելով Hash քարտեզ

Ալգորիթմ `հարակից զանգվածի լեյկոդի խնդրի համար

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. Այստեղ մենք որպես ստեղն օգտագործում ենք (sum + n): Բայց մենք կարող էինք նաև գումարն ուղղակիորեն օգտագործել: Բայց եթե մենք օգտագործում ենք (sum + n) որպես բանալի, ապա HashMap- ի փոխարեն կարող ենք նաև զանգված օգտագործել: Քանի որ այդ դեպքում կարող ենք հավաստիացնել, որ (sum + n)> = 0 և զանգվածի ինդեքսավորումը սկսվում է 0-ից:

Կոդ

C ++ ծրագիր ՝ հարակից զանգվածի Leetcode- ի խնդիրը լուծելու համար
#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
Java ծրագրի հարակից զանգված Leetcode- ի խնդիրը լուծելու համար
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

Բարդության վերլուծություն

Timeամանակի բարդություն

ՎՐԱ) որտեղ n- ը տրված զանգվածում տարրերի քանակն է a []: Քանի որ e- ն օգտագործել է unordered_map / HashMap- ը, մենք կարողացանք հասնել O (N) ժամանակի, քանի որ HashMap- ը թույլ է տալիս O (1) ժամանակին կատարել ներդիրի որոնում, ջնջում:

Տիեզերական բարդություն

ՎՐԱ) քանի որ մենք օգտագործել ենք N լրացուցիչ տարածք: Քանի որ մենք օգտագործել ենք HashMap գովազդը, պահպանում է N տարրերի մասին տեղեկատվությունը, ամենավատ դեպքում, որը կարող է ունենալ N տարր: