Ավելացրեք Երկուական Leetcode լուծում


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Amazon facebook Microsoft
Մաթեմատիկա String

Խնդիրի հայտարարություն

Հաշվի առնելով երկու երկուական տողերը a և b, մենք պետք է ավելացնենք այս երկու տողերը և ապա արդյունքը վերադարձնենք որպես երկուական լար: Երկուական տողը այն տողերն են, որոնք պարունակում են ընդամենը 0 և 1:

Օրինակ

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

Մոտեցում

Ավելացրեք Երկուական Leetcode լուծում

Երկու երկուական տող ավելացնելու համար մենք պետք է հատիկ առ մաս կատարենք: Ինչպես գիտենք, լրացումը կատարվում է աջ ծայրից ՝ շարժվելով դեպի ձախ բիթեր: Ուստի նախ պետք է հետ տանք տրված տողերը, ապա կարողանանք կատարել 0 բիտից սկսած դրա բիթերի գումարումը:
Բիթ լրացման հաջորդականությունը պահելու համար մենք կարող ենք ստեղծել լարային փոփոխական res և կցել երկու բիթի գումարը և կրել վերջում res տող յուրաքանչյուր բիթի դիրքի համար: Վերջապես մենք կվերադարձնենք res լարային ելքի համար:

Ալգորիթմ

  • Հակադարձել տրված տողերը:
  • Ստեղծեք դատարկ լար և ա կրել փոփոխական Նախնական կրել 0- ի հետ:
  • Այժմ կրկնում ենք տրված տողը մի որոշ ժամանակահատվածում և տեղափոխման հետ մեկտեղ ավելացնում ենք առաջին և երկրորդ լարերի բիտը: Այժմ ըստ հավելման արժեքի, ստացվող բիտը կցեք 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

Երկուական 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 լուծում

Timeամանակի բարդություն

O (առավելագույն (N, M)): Որտեղ N և M մուտքային տողի երկարություններն են: Քանի որ երկուսն էլ տողը գծային կերպով անցնում ենք մեկ օղակում, ժամանակի բարդությունը հավասար կլինի առավելագույն երկարությանը `երկու մուտքային տողերից:

Տիեզերական բարդություն 

O (առավելագույն (N, M)): Արդյունքն ավելացումից հետո լարում պահելու համար մեզ անհրաժեշտ է մի լար, որի չափը հավասար է մուտքային տողերի առավելագույն երկարությանը: