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

目录

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();
}
上一篇:反卷积(Transposed Convolution)


下一篇:2.两数相加