Дадайце двайковае рашэнне Leetcode


Узровень складанасці Лёгка
Часта пытаюцца ў амазонка facebook Microsoft
Матэматыка Радок

Пастаноўка праблемы

Улічваючы два двайковыя радкі a і b, мы павінны дадаць гэтыя дзве радкі, а потым вярнуць вынік у выглядзе двайковай радкі. Бінарныя радкі - гэта радкі, якія ўтрымліваюць толькі 0 і 1.

Прыклад

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

Падыход

Дадайце двайковае рашэнне Leetcode

Для дадання дзвюх двайковых радкоў мы павінны выконваць складанне па бітах. Як мы ведаем, складанне выконваецца з правага канца, рухаючыся да левых бітаў. Таму мы павінны спачатку адмяніць дадзеныя радкі, а потым мы можам выканаць складанне яго бітаў, пачынаючы з індэкса 0.
Для захоўвання паслядоўнасці бітавага складання мы можам стварыць радкавую зменную дазволу і дадайце суму двух бітаў і перанясіце ў канцы дазволу радок для кожнай бітавай пазіцыі. Нарэшце мы вернем дазволу радок для вываду.

Алгарытм

  • Адвярнуць дадзеныя радкі назад.
  • Стварыце пусты радок і несці зменнай. Ініцыялізацыя несці з 0.
  • Цяпер перабярыце дадзены радок у цыкле while і дадайце біт першай і другой радкі разам з пераноссем. Цяпер у адпаведнасці са значэннем складання дадайце выніковы біт у радок 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)): Для захоўвання выніку ў радку пасля складання нам патрэбна радок, памер якой роўны максімальнай даўжыні ўваходных радкоў.