LeetCode67-二进制求和

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/add-binary/

中文链接：https://leetcode-cn.com/problems/add-binary/

题目详述

给定两个二进制字符串，返回他们的和（用二进制表示）。

输入为非空字符串且只包含数字 1 和 0。

示例 1:

1
2
输入: a = "11", b = "1"
输出: "100"

示例 2:

1
2
输入: a = "1010", b = "1011"
输出: "10101"

题目详解

  • 类似于 LeetCode2-两数相加，模拟竖式加法。
  • 从低为到高位诸位遍历，诸位相加得到结果，并得到进位。
  • 注意遍历结束后进位可能不为 0，这部分也需要前加上。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class LeetCode_00067 {

    public String addBinary(String a, String b) {
        int i = a.length() - 1;
        int j = b.length() - 1;
        int carry = 0;
        StringBuilder res = new StringBuilder();
        while (i >= 0 || j >= 0) {
            carry += (i >= 0 ? a.charAt(i--) - '0' : 0) + (j >= 0 ? b.charAt(j--) - '0' : 0);
            res.append(carry & 1);
            carry >>= 1;
        }
        if (carry != 0) {
            res.append(carry);
        }
        return res.reverse().toString();
    }
}