Bitişik Array Leetcode

Problem bəyanat

“Bitişik Array Leetcode” problemi sizə verildiyini bildirir array n ölçülü a [] yalnız 1 və 0-dan ibarətdir. Tapın ən uzun subarray burada 1-lərin sayı 0-lara bərabərdir.

misal

Pin

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

1 to 6

İzahat: 1-dən 6-ya qədər bir subarray seçib 6-cı uzunluğun ən yaxşı nəticəsini veririk. 1-dən 6-a qədər olan bitişik massivin 3-ü və 3-ü var. Burada 0 əsaslı indeksləşdirmə hesab etdik.

a[ ] = {1, 1}

No such subarray

Yanaşma

Sadəlövh metod

Mümkün olan bütün alt analizləri yaradın. 1-in sayının 0-ın sayına bərabər olan hər hansı bir alt bölməsinin olub olmadığını yoxlayın. Alt dizinin sol və sağ sərhədləri üçün iki i və j göstəricilərindən istifadə edirik. Sonra 0-ı -0 ilə əvəz etdikdən sonra, i-dən j-yə qədər subarray cəminin cəmi = 1 olub olmadığını yoxlayırıq. Əgər bu doğrudursa, şərtlərə cavab verən alt bölmə tapdıq. İndi cavabımızı yeniləyirik.

Bitişik sıra leetcod problemi üçün alqoritm

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.

Kodu

Bitişik Array Leetcode problemini həll etmək üçün C ++ proqramı

#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

Bitişik Array Leetcode problemini həll etmək üçün Java Proqramı

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

Buradan bəri bir göstəricini sabit saxlayarkən sıra boyunca gəzirdik. -Nin bir polinom zaman mürəkkəbliyinə nail olduq  O (N²) burada n - verilən bir [] massivindəki elementlərin sayı.

Kosmik Mürəkkəblik

O (1) çünki daimi əlavə yer istifadə edirdik. Yalnız dəyişənlərin daimi sayını yaratdıq. Lakin ilkin giriş massivindən başqa heç bir sıra istifadə etməyib. Ancaq proqram bütövlükdə giriş elementlərini saxlamaq üçün bir sıra istifadə etdiyimiz üçün O (N) kosmik mürəkkəbliyə malikdir.

Hash xəritəsi istifadə olunur

Bitişik sıra leetcod problemi üçün alqoritm

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".

Burada etdiklərimiz, sadəcə cəmi 0 olan ən böyük alt bölməni tapmaq lazım olduqda. Nə edirsək, cəmi prefiksini götürürük və eyni cəmi tapa biləcəyimiz bir yer varsa xəritəmizə daxil oluruq. Sonra +1 xəritədə saxlanılan dəyərdən indiki indeksə qədər olan subarray cəmi 0-a bərabərdir. Burada (sum + n) düyməsini istifadə edirik. Ancaq biz birbaşa cəmdən də istifadə edə bilərdik. Lakin (sum + n) düyməsini açar kimi istifadə etsək, HashMap əvəzinə bir sıra da istifadə edə bilərik. Çünki onda (sum + n)> = 0 və sıra indeksləşdirməsinin 0-dan başlayacağına əmin ola bilərik.

Kodu

Bitişik Array Leetcode problemini həll etmək üçün C ++ proqramı

#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

Bitişik Array Leetcode problemini həll etmək üçün Java Proqramı

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N) burada n - verilən bir [] massivindəki elementlərin sayı. E unordered_map / HashMap istifadə etdiyindən, O (N) vaxt əldə edə bildik, çünki HashMap O (1) -ə daxiletmə axtarışını, silməsini həyata keçirməyə imkan verir.

Kosmik Mürəkkəblik

O (N) çünki N əlavə yer istifadə etdik. Bir HashMap reklamından istifadə etdiyimiz üçün N elementi haqqında məlumatları, ən pis halda N elementi ola bilər.