Binary Leetcode Solution кошуу


Кыйынчылык деңгээли жеңил
Көп суралган Amazon Facebook Microsoft
Math аркан

Маселени билдирүү

Берилген эки бинардык саптар a жана b, биз ушул эки сапты кошуп, натыйжаны экилик сап катары кайтарышыбыз керек. Эки сап - бул 0 жана 1 гана орун алган саптар.

мисал

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

жакындоо

Binary Leetcode Solution кошуу

Эки бинардык сапты кошуу үчүн, кошумчаны аз-аздан аткарышыбыз керек. Белгилүү болгондой, кошуу оң биттен сол биттерге карай жылдырылат. Ошондуктан, алгач берилген саптарды артка кайтарышыбыз керек, андан кийин анын биттерин 0 индексинен баштап толуктай алабыз.
Бит кошуу ырааттуулугун сактоо үчүн сап өзгөрмөсүн түзө алабыз чечилиштеги жана эки биттин суммасын кошуп, аягында алып жүрүңүз чечилиштеги ар бир бит позициясы үчүн сап. Акыр-аягы, биз чечилиштеги чыгаруу үчүн сап.

Algorithm

  • Берилген саптарды тескери буруңуз.
  • Бош сап түзүңүз жана а көтөрүп өзгөрүлмө. Баштоо көтөрүп 0 менен.
  • Эми берилген саптын үстүнөн кайталап, кайталаңыз жана көтөрүп жүрүү менен бирге биринчи жана экинчи саптын битин кошуңуз. Эми кошуунун маанисине ылайык, натыйжалуу битти res сапына кошуп, жаңыртыңыз көтөрүп кийинки бит үчүн.
  • Акыры бизде сап бар, бирок ал тескери тартипте, анткени биз ыңгайлуу болушубуз үчүн тескери киргизилген сапта кошумчаларды жасадык. Демек, чыккан сапты артка кайтарып, акыры аны кайтарыңыз.

ишке ашыруу

Binary Leetcode Solution кошуу үчүн 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

Binary Leetcode Solution кошуу үчүн 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

Binary Leetcode Solution кошуу үчүн татаалдыкты талдоо

Убакыт татаалдыгы

O (max (N, M)): Бул жерде N жана M - киргизилген саптын узундугу. Бир эле циклде эки сапты тең сызык бойдон кесип өтсөк, убакыттын татаалдыгы эки кириш саптын максималдуу узундугуна барабар болот.

Космостун татаалдыгы 

O (max (N, M)): Жыйынтыкты кошуудан кийин сапта сактоо үчүн көлөмү кириш саптарынын узундугунун максимумуна барабар сап керек.