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

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

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

题目地址：https://leetcode.com/problems/add-binary/description/

题目描述

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 日 —— 周六快乐