이진 Leetcode 솔루션 추가

난이도 쉽게
자주 묻는 질문 아마존 Facebook Microsoft
알고리즘 코딩 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions 수학 조회수 110

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

문제 정책

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

a = "11", b = "1"
"100"
a = "1010", b = "1011"
"10101"

접근

이진 Leetcode 솔루션 추가

두 개의 이진 문자열을 추가하려면 비트 단위로 추가를 수행해야합니다. 우리가 알고 있듯이 덧셈은 오른쪽 끝에서 왼쪽 비트로 이동합니다. 그러므로 우리는 주어진 문자열을 먼저 뒤집어 야하며 그 다음 인덱스 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;
}
10101

바이너리 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));
    }
}
10101

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

시간 복잡성

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

공간 복잡성 

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

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