연속 배열 Leetcode

난이도 중급
자주 묻는 질문 아마존 Facebook 구글
알고리즘 배열 코딩 해싱 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions조회수 91

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 정책

“Contiguous Array 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 개의 XNUMX이 있습니다. 여기서는 XNUMX 기반 인덱싱을 고려했습니다.

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

접근

순진한 방법

가능한 모든 하위 배열을 생성합니다. 1의 수가 0의 수와 같은 하위 배열이 있는지 확인합니다. 하위 배열의 왼쪽과 오른쪽 경계에 두 개의 포인터 i와 j를 사용합니다. 그런 다음 0을 -0로 바꾼 후 i에서 j까지의 부분 배열 합계가 합계 = 1인지 확인합니다. 그것이 사실이라면 조건을 만족하는 하위 배열을 찾은 것입니다. 이제 답변을 업데이트합니다.

연속 배열 leetcode 문제에 대한 알고리즘

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.

암호

연속 배열 Leetcode 문제를 해결하는 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
Contiguous Array Leetcode 문제를 해결하는 Java 프로그램
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

복잡성 분석

시간 복잡성

여기서부터 우리는 포인터를 고정한 상태로 배열을 순회하고있었습니다. 우리는 다음과 같은 다항식 시간 복잡도를 얻었습니다.  의 위에2) 여기서 n은 주어진 배열 a []에있는 요소의 수입니다.

공간 복잡성

O (1) 일정한 여유 공간을 사용했기 때문입니다. 우리는 일정한 수의 변수 만 만들었습니다. 그러나 초기 입력 배열 이외의 배열을 사용하지 않았습니다. 그러나 입력 요소를 저장하기 위해 배열을 사용했기 때문에 프로그램 전체는 O (N) 공간 복잡성이 있습니다.

해시 맵 사용

연속 배열 leetcode 문제에 대한 알고리즘

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부터 시작하도록 보장 할 수 있기 때문입니다.

암호

연속 배열 Leetcode 문제를 해결하는 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
Contiguous Array Leetcode 문제를 해결하는 Java 프로그램
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

복잡성 분석

시간 복잡성

의 위에) 여기서 n은 주어진 배열 a []에있는 요소의 수입니다. e가 unorder_map / HashMap을 사용했기 때문에 HashMap은 O (1) 시간이 삽입 검색, 삭제를 수행 할 수 있도록 허용하기 때문에 O (N) 시간을 달성 할 수있었습니다.

공간 복잡성

의 위에) N 개의 추가 공간을 사용했기 때문입니다. HashMap 광고를 사용했기 때문에 N 요소에 대한 정보가 저장되었으므로 최악의 경우 N 요소를 가질 수 있습니다.

균열 시스템 설계 인터뷰
Translate »