LeetCode_字符串_简单_67.二进制求和

目录

• 1.题目
• 2.思路
• 3.代码实现（Java）

1.题目

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

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

示例 1：

输入: a = “11”, b = “1”

输出: “100”

示例 2：

输入: a = “1010”, b = “1011”

输出: “10101”

提示：

每个字符串仅由字符 ‘0’ 或 ‘1’ 组成。

1 <= a.length, b.length <= 104

字符串如果不是 “0” ，就都不含前导零。

来源：力扣（LeetCode）

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

2.思路

（1）将字符串 a 和 b 转化成十进制数并求和，然后再转化为二进制数即可。不过当题目中字符串的长度非常大时，就有可能超过Java所能表示的范围，所以该思路具有一定的局限性。

（2）采用整数加法中列竖式的方法来求解本题，即将这两个二进制字符串从低位到高位逐位相加，并且记录相加过程中产生的进位，将其考虑到下一轮运算中即可。

3.代码实现（Java）

//（1）思路1
public String addBinary(String a, String b) {
    /*
        toBinaryString(int i):返回int变量的二进制表示的字符串
        Integer.parseInt(s,2):将字符串s转换为二进制的整数
    */
    return Integer.toBinaryString(Integer.parseInt(a,2)+Integer.parseInt(b,2));
}
           

//（2）思路2
public String addBinary(String a, String b) {
	//代码来自本题官方题解
	/*
		在使用 StringBuffer类时，每次都会对 StringBuffer对象本身进行操作，而不是生成新的对象，
		所以如果需要对字符串进行修改推荐使用StringBuffer，而此题可好需要需要对字符串进行修改。
	*/
    StringBuffer ans = new StringBuffer();
	//carry表示进位
    int n = Math.max(a.length(), b.length()), carry = 0;
    for (int i = 0; i < n; ++i) {
		//将a和b的最低位依次进行相加
        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之后
        ans.append((char) (carry % 2 + '0'));
		/* 
			进行上述的一次计算后，carry的可能取值为0、1或2
			1.carry=0，说明a、b当前位上的值均为'0'，没有进位
			2.carry=1，说明a、b当前位上的值有一个位'0'，有一个为'1'，没有进位
			3.carry=2，说明a、b当前位上的值均为'1'，产生进位
			当进行下一轮计算时，只有当carry=2时才产生了进位，此时需要使carry变成1，
			而其它情况下没有产生进位，则使carry变成0即可，而carry/=2正好满足要求
		*/
        carry/=2;
    }
	//如果进位大于0，则需要向高位添加一个"1"
    if (carry > 0) {
        ans.append('1');
    }
	/*
		reverse():将字符序列进行反转
		例如s="123"，那么s.reverse()之后，s="321"
	*/
    ans.reverse();
	//以字符串的形式进行返回
    return ans.toString();
}