Leetcode(67) 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:

1
2
Input: a = "11", b = "1"
Output: "100"

Example 2:

1
2
Input: a = "1010", b = "1011"
Output: "10101"

解法

与模拟加法实现的过程相同，只不过是二进制而已，注意不同长度的字符相加和进位的处理，同时记得处理多余的前导0。

具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class Solution {
    public String addBinary(String a, String b) {
        StringBuffer res = new StringBuffer();
        StringBuffer x = new StringBuffer(a);
        x.reverse();
        StringBuffer y = new StringBuffer(b);
        y.reverse();
        if (x.length() < y.length()) {
            int add0 = y.length() - x.length();
            while (add0 > 0) {
                x.append('0');
                add0--;
            }
        } else {
            int add0 = x.length() - y.length();
            while (add0 > 0) {
                y.append('0');
                add0--;
            }
        }
        int tmp = 0;
        for (int i = 0; i < x.length(); i++) {
            if (x.charAt(i) == '0' && y.charAt(i) == '1') {
                if (tmp == 0) {
                    res.append('1');
                } else {
                    res.append('0');
                    tmp = 1;
                }
            }
            if (x.charAt(i) == '1' && y.charAt(i) == '0') {
                if (tmp == 0) {
                    res.append('1');
                } else {
                    res.append('0');
                    tmp = 1;
                }
            }
            if (x.charAt(i) == '0' && y.charAt(i) == '0') {
                if (tmp == 0) {
                    res.append('0');
                } else {
                    res.append('1');
                    tmp = 0;
                }
            }
            if (x.charAt(i) == '1' && y.charAt(i) == '1') {
                if (tmp == 0) {
                    res.append('0');
                    tmp = 1;
                } else {
                    res.append('1');
                    tmp = 1;
                }
            }
        }
        if (tmp == 1) {
            res.append('1');
        }
        res.reverse();
        while (res.charAt(0) == '0' && res.length() > 1) {
            res.deleteCharAt(0);
        }
        return res.toString();
    }
}