【LeetCode】67. Add Binary 解题报告（Python）

作者：负雪明烛
id： fuxuemingzhu
个人博客： http://fuxuemingzhu.cn/

题目描述

Given two binary strings, return their sum (also a binary string).

The input strings are both non-empty and contains only characters 1 or 0.

Example 1:

Input: a = "11", b = "1"

Output: "100"

Example 2:

Input: a = "1010", b = "1011"

Output: "10101"

题目大意

使用字符串表示的二进制数，求他们的和，结果应该也是个字符串。

解题方法

BigInteger类

import java.math.BigInteger;

public class Solution {

    public String addBinary(String a, String b) {

        BigInteger a_ = new BigInteger(a,2);

        BigInteger b_ = new BigInteger(b,2);

        return a_.add(b_).toString(2);

    }

}

模拟加法

使用的方法简单直接，之前也有类似的题。我先把两个字符串拼接成一样长的，然后再计算，能省去很多判断。如果最后的carry还存在的话，那么需要再加上一个1.

class Solution(object):

    def addBinary(self, a, b):

        """

        :type a: str

        :type b: str

        :rtype: str

        """

        M, N = len(a), len(b)

        if M < N:

            a = "0" * (N - M) + a

        else:

            b = "0" * (M - N) + b

        stack1 = list(a)

        stack2 = list(b)

        res = ""

        carry = 0

        while stack1 and stack2:

            s1, s2 = stack1.pop(), stack2.pop()

            cursum = int(s1) + int(s2) + carry

            if cursum >= 2:

                cursum %= 2

                carry = 1

            else:

                carry = 0

            res = str(cursum) + res

        if carry:

            res = "1" + res

        return res

日期

2017 年 8 月 17 日
2018 年 11 月 24 日 —— 周六快乐

巴特西