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

红太狼 2023-10-06 19:27 57阅读 0赞

#### 目录 ####

*  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）列竖式  
思路参考[本题官方题解][Link 1]。采用整数加法中**列竖式**的方法来求解本题，即将这两个二进制字符串从低位到高位逐位相加，并且记录相加过程中产生的进位，将其考虑到下一轮运算中即可。

## 3.代码实现（Java） ##

//思路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————列竖式
    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();
    }

[Link 1]: https://leetcode-cn.com/problems/add-binary/solution/er-jin-zhi-qiu-he-by-leetcode-solution/