Добавете двоично решение с Leetcode


Ниво на трудност Лесно
Често задавани в Амазонка Facebook Microsoft
Математически Низ

Декларация за проблема

Дадени две двоични струни a и b, трябва да добавим тези два низа и след това да върнем резултата като двоичен низ. Двоичен низ са низовете, които съдържат само 0s и 1s.

Пример

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

Подход

Добавете двоично решение с Leetcode

За добавяне на два двоични низа трябва да изпълняваме добавяне малко по малко. Както знаем, добавянето се извършва от десния край, придвижвайки се към левите битове. Затова първо трябва да обърнем дадените низове и след това можем да извършим добавяне на неговите битове, започвайки от индекс 0.
За съхранение на последователност за добавяне на битове можем да създадем низ променлива ВЕИ и добавете сумата от два бита и пренесете в края на ВЕИ низ за всяка битова позиция. Накрая ще върнем ВЕИ низ за изход.

алгоритъм

  • Обърнете дадените низове.
  • Създайте празен низ и a нося променлива. Инициализиране нося със 0.
  • Сега прегледайте дадения низ в цикъл while и добавете бит от първия и втория низ заедно с carry. Сега според стойността на добавяне добавете получения бит към res низ и също така актуализирайте нося за следващия бит.
  • Най-накрая имаме изходен низ, но той е в обратен ред, защото за наше удобство сме извършили добавяне на обърнат входен низ. Затова обърнете изходния низ и накрая го върнете.

изпълнение

Програма C ++ за добавяне на двоично решение с Leetcode

#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

Java програма за добавяне на двоично Leetcode решение

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)): За съхраняване на резултата в низ след добавяне се нуждаем от низ, чийто размер е равен на макс. Дължина на входните низове.