【leetcode】002二进制加法

一、题目概述

给定两个 01 字符串 a 和 b ，请计算它们的和，并以二进制字符串的形式输出。输入为 非空 字符串且只包含数字 1 和 0。

二、代码思想

• 采用模拟二进制运算的思想，与十进制类似.
• 具体思路：
• 1、获取两个字符串的数组，数组的每一位代表一个二进制数。
• 2、依次遍历两个数组，对不同位上的二进制数进行计算。
• 3、计算方法：carry为进位，Aarray[i] Barray[i] 分别为对应位上的二进制数。
• 每个位置上的数：(carry+Aarray[i]+Barray[i])%2。
• 进位的计算：carry=(carry+Aarray[i]+Barray[i])向下取整。
• 4、 为了保证计算的方便性，我们可以对字符串进行一个倒置，这样从0开始遍历字符串就相当于从低位开始遍历。
• 5、 为了保证计算的正确性，我们需要比较两个字符串的长度，先对短串部分进行计算，然后再单独对多出来的串进行计算。
• 6、 注意别忘了如果最后一位有进位，那么我们应该在最后的结果上加一个字符: ‘1’.

三、具体实现

class Solution {
    public String addBinary(String a, String b) {
    //使用StringBuilder更方便：字符串倒置以及字符的添加
        StringBuilder aSb = new StringBuilder(a);
        StringBuilder bSb = new StringBuilder(b);
        a = aSb.reverse().toString();
        b = bSb.reverse().toString();
        char aArray[] = a.toCharArray();
        char bArray[] = b.toCharArray();
        StringBuilder result = new StringBuilder("");
        int aLength = a.length();
        int bLength = b.length();
        int minLength=0;
        int maxLength=0;
        int carry = 0;
        int flag=-1;//flag=0则a长，flag=1则b长。
        System.out.println(1>1);//false
        if(aLength>bLength){
            maxLength=aLength;
            minLength=bLength;
            flag=0;
        }else if(aLength<bLength){
            maxLength=bLength;
            minLength=aLength;
            flag=1;
        }else{
            flag=-1;
            minLength=aLength;
            maxLength=aLength;
        }

        //System.out.println((aArray[0] + bArray[0]+ 2));
        for (int i = 0; i < minLength; i++) {
            result.append((aArray[i] + bArray[i] + carry) % 2);
            //System.out.println(result);
            //System.out.println("carry/2:" + (aArray[i]-48 + bArray[i]-48 + carry) / 2);
            if (((aArray[i]-48 + bArray[i]-48 + carry) / 2) >= 1) {
                carry = 1;
            } else {
                carry = 0;
            }
            System.out.println(carry);
        }
        switch (flag){
            case 1:{
                for (int j=minLength;j<maxLength;j++){
                    result.append((bArray[j]-48+carry)%2);
                    if((bArray[j]-48+carry)/2>=1){
                        carry=1;
                    }else{
                        carry=0;
                    }
                }
                break;
            }
        case 0:{
            for (int j=minLength;j<maxLength;j++){
                result.append((aArray[j]-48+carry)%2);
                if((aArray[j]-48+carry)/2>=1){
                    carry=1;
                }else{
                    carry=0;
                }
            }
            break;
        }
    }
        if (carry==1) result.append('1');
        return result.reverse().toString();
    }
}
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
67
68
69
70
71

官方题解：实在简洁，没脸看了哈哈

class Solution {
    public String addBinary(String a, String b) {
        StringBuffer ans = new StringBuffer();

        int n = Math.max(a.length(), b.length()), carry = 0;
        for (int i = 0; i < n; ++i) {
            carry += i < a.length() ? (a.charAt(a.length() - 1 - i) - '0') : 0;
            carry += i < b.length() ? (b.charAt(b.length() - 1 - i) - '0') : 0;
            ans.append((char) (carry % 2 + '0'));
            carry /= 2;
        }

        if (carry > 0) {
            ans.append('1');
        }
        ans.reverse();

        return ans.toString();
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/JFETK5/solution/er-jin-zhi-jia-fa-by-leetcode-solution-fa6t/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
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

四、参考资料

0和1的AciII码： ascii
char字符的运算：char跟int类型运算，计算的是ascii码
将字符串反转的几种方法：字符串反转

• 使用Sringbuilder类
• 转成char数组，然后反遍历
• 转成byte数组，然后进行反遍历