바이너리 Leetcode 솔루션 추가-TutorialCup 솔루션

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

차례

문제 정책

두 개의 바이너리가 주어짐 문자열 a와 b,이 두 문자열을 추가 한 다음 결과를 이진 문자열로 반환해야합니다. 이진 문자열은 0과 1 만 포함 된 문자열입니다.

예

a = "11", b = "1"

"100"

a = "1010", b = "1011"

"10101"

접근

핀

두 개의 이진 문자열을 추가하려면 비트 단위로 추가를 수행해야합니다. 우리가 알고 있듯이 덧셈은 오른쪽 끝에서 왼쪽 비트로 이동합니다. 그러므로 우리는 주어진 문자열을 먼저 뒤집어 야하며 그 다음 인덱스 0부터 시작하여 비트를 더할 수 있습니다.
비트 추가 시퀀스를 저장하기 위해 문자열 변수를 만들 수 있습니다. 고해상도 두 비트의 합계를 추가하고 고해상도 각 비트 위치에 대한 문자열. 마지막으로 우리는 고해상도 출력 문자열입니다.

암호알고리즘

주어진 문자열을 뒤집습니다.
빈 문자열을 만들고 나르다 변하기 쉬운. 초기화 나르다 0와 함께.
이제 주어진 문자열을 반복합니다. while 루프 캐리와 함께 첫 번째 및 두 번째 문자열의 비트를 추가합니다. 이제 추가 값에 따라 결과 비트를 res 문자열에 추가하고 업데이트합니다. 나르다 다음 비트.
마지막으로 출력 문자열이 있지만 편의를 위해 반전 된 입력 문자열에 더하기를 수행했기 때문에 역순입니다. 따라서 출력 문자열을 반대로하고 마지막으로 반환합니다.

실시

바이너리 Leetcode 솔루션 추가를위한 C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;

string addBinary(string a, string b) 
{      
    int carry=0;
    string res="";

    reverse(a.begin(),a.end()); 
    reverse(b.begin(),b.end());

    int i=0,sum;
    while(i<a.size() || i<b.size())
    {
        sum= carry;

        if(i<a.size()) sum+= a[i]-'0';
        if(i<b.size()) sum+= b[i]-'0';

        if(sum==0) carry=0, res+='0';
        else if(sum==1)  carry=0, res+='1';
        else if(sum==2)carry=1, res+='0';
        else carry=1, res+='1';


        i++;
    }


    if(carry==1)  res+='1';

    reverse(res.begin(),res.end());
    return res;
        
}
int main()
{
  string a = "1010"; 
  string b = "1011";
  cout<<addBinary(a,b)<<endl;
}

바이너리 Leetcode 솔루션 추가를위한 Java 프로그램

import java.util.*;

class Rextester{
    
    public static String addBinary(String a, String b) 
    {      
        int carry=0;

        StringBuilder s1=new StringBuilder(a);
        StringBuilder s2=new StringBuilder(b);
        StringBuilder res=new StringBuilder();

        s1.reverse(); 
        s2.reverse();

        int i=0,sum;
        while(i<a.length() || i<b.length())
        {
            sum= carry;

            if(i<a.length()) sum+= s1.charAt(i)-'0';
            if(i<b.length()) sum+= s2.charAt(i)-'0';

            if(sum==0) 
            {
                 carry=0;
                 res.append('0');
            }
            if(sum==1) 
            {
                 carry=0;
                 res.append('1');
             }
            if(sum==2)
            {
                carry=1;
                res.append('0');
            }
           if(sum==3) 
            {
                carry=1;
                res.append('1');
            }

            i++;
        }
    
        if(carry==1)   res.append('1');

        res.reverse();
        return res.toString();
        
    }
    
  public static void main(String args[])
    {
        String a = "1010"; 
        String b = "1011";
        System.out.println(addBinary(a,b));
    }
}

이진 Leetcode 솔루션 추가를위한 복잡성 분석

시간 복잡성

O (최대 (N, M)) : 여기서 N과 M은 입력 문자열의 길이입니다. 단일 루프에서 두 문자열을 선형으로 순회하므로 시간 복잡도는 두 입력 문자열 중 최대 길이와 같습니다.

공간 복잡성

O (최대 (N, M)) : 추가 후 문자열에 결과를 저장하려면 입력 문자열의 최대 길이와 크기가 같은 문자열이 필요합니다.