添加二進制Leetcode解決方案


難度級別 容易獎學金
經常問 亞馬遜 Facebook Microsoft微軟
數學

問題陳述

給定兩個二進制 字符串 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)): 為了在加法之後將結果存儲在字符串中,我們需要大小等於輸入字符串最大長度的字符串。