문자열 압축

난이도 중급
자주 묻는 질문 아마존 Apple 시트릭스 Expedia Facebook 골드만 삭스 IBM Microsoft Yandex 주차
조회수 128

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

. 문자열 압축 문제, 우리는 char 유형의 배열 a []를 제공했습니다. 특정 문자의 문자 및 개수로 압축합니다 (문자 개수가 1이면 유일한 문자는 압축 된 배열에 저장됩니다). 압축의 길이 정렬 원래 배열보다 작아야합니다. 압축 된 배열의 길이를 반환합니다.

문자열 압축

입력 : a [] = { 'a', 'a', 'a', 'b', 'b'}

출력 : 4 (압축 된 어레이는 { 'a', '3', 'b', '2'}가 됨)

입력 : a [] = { 'a'}

출력 : 1 (압축 된 배열은 { 'a'}가됩니다. 개수 = 1이므로 압축 된 배열은 개수가 아닌 문자 만 포함합니다.)

문자열 압축 알고리즘

  1. n 크기의 문자 배열을 초기화합니다.
  2. 변수 결과를 0으로 선언하고 1로 계산합니다.
  3. 배열을 탐색하고 비슷한 종류의 문자를 계산합니다.
  4. 문자의 수가 1이면 압축 된 배열에있는 유일한 문자로 간주되므로 결과를 1 씩 증가시킵니다.
  5. 그렇지 않으면 문자와 개수 모두에 대해 결과를 2 씩 증가시킵니다.
  6. 결과를 인쇄하십시오.

시간 복잡성 : O (n) 여기서 n은 배열의 요소 수입니다. 모든 요소를 ​​한 번 탐색하므로 시간 복잡도는 O (n)입니다.

보조 공간 : O (1) 작업을 수행하는 데 보조 공간을 사용하지 않기 때문입니다.

문자열 압축을위한 C ++ 프로그램

#include <bits/stdc++.h> 
using namespace std; 
  
void compression(char a[], int n){ 
    
    int result = 0; 
    for(int i=0; i<n; i++){ 
  
        int count = 1; 
        while(i<n-1 && a[i] == a[i + 1]){ 
            count++; 
            i++; 
        } 
        
        if(count==1){
            result++;
        }
        else{
            result = result + 2;
        }
    } 
    cout<<result;
} 
  
int main(){
    
    char a[] = {'a', 'a', 'a', 'b', 'b'}; 
    int n = sizeof(a)/sizeof(a[0]);
    
    compression(a, n); 
    
    return 0; 
}
4

문자열 압축을위한 자바 프로그램

class StringCompression{ 
    
    static void compression(char[] a, int n){ 
        
        int result = 0;
        
        for(int i=0; i<n; i++){ 
            int count = 1; 
            while(i<n-1 && a[i] == a[i+1]){ 
                count++; 
                i++; 
            } 
  
            if(count==1){
                result++;
            }
            else{
                result = result + 2;
            } 
        } 
        
        System.out.println(result);
    } 
  
    public static void main(String[] args){
        
        char[] a = {'a', 'a', 'a', 'b', 'b'}; 
        int n = a.length;
        
        compression(a, n); 
    } 
}
4

참조

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