剑指 Offer II 002二进制加法一文全搞定逐位相加

ゞ浴缸里的玫瑰 2024-03-27 10:31 71阅读 0赞

给定两个 01 字符串 a 和 b ，请计算它们的和，并以二进制字符串的形式输出。

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

示例 1:

输入: a = "11", b = "10"  
输出: "101"  
示例 2:

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

提示：

每个字符串仅由字符 '0' 或 '1' 组成。  
1 <= a.length, b.length <= 10^4  
字符串如果不是 "0" ，就都不含前导零。

方法一：模拟加法运算

题解思路：

先举一个整数的例子，1274+181

1274

\+ 181

= 1455

十进制整数中，当数字满10，则我们进1位，比如7+8的时候是15，则我们保留5（可以想到用余数）然后再把1保存下来加在下一位，而位置空的地方我们选择0来代替（有数字则数字，没数字则0），然后存放在数组、或者字符串上（字符串的话要用StringBuilder来动态存储）

\+ 10

= 101

回到二进制的加法中，则是满2进1位，思路和其他的一样

class Solution {
        public String addBinary(String a, String b) {
            //存放动态的结果,需要的是Builder
            StringBuilder res = new StringBuilder();
            int carry = 0;
            //获取最右边的下标
            int alen = a.length() - 1;
            int blen = b.length() - 1;
        while (alen >= 0 || blen >= 0) {
            int x = alen < 0 ? 0 : a.charAt(alen) - '0';
            int y = blen < 0 ? 0 : b.charAt(blen) - '0';
    
            int sum = x + y + carry;
            res.append(sum % 2);
            carry = sum / 2;
    
            alen--;
            blen--;
        }
        //最后余下的一位
        if (carry != 0) res.append(carry);
        return res.reverse().toString();
        }
    }