67. 二进制求和——【Leetcode每日一题】

た入场券 2024-03-24 11:34 11阅读 0赞

### 67. 二进制求和 ###

给你两个二进制字符串 `a` 和 `b` ，以二进制字符串的形式返回它们的和。

##### 示例 1： #####

> 输入:a = “11”, b = “1”  
> 输出：“100”

##### 示例 2： #####

> 输入：a = “1010”, b = “1011”  
> 输出：“10101”

##### 提示： #####

*   1 < = a . l e n g t h , b . l e n g t h < = 1 0 4 1 <= a.length, b.length <= 10^4 1<=a.length,b.length<=104
 *  `a` 和 `b` 仅由字符 ‘0’ 或 ‘1’ 组成
 *  字符串如果不是 “0” ，就不含前导零

#### 思路： ####

模拟位运算：

*  从两个字符串的末尾，一步一步运算，满2进位；

优化：

*  任意一位相加，要加三个数，分别为:
    
     *  `a` 的第 `i` 位，
     *  `b` 的第 `i` 位 ，
     *  以及前一位的进位 `carry`

#### 代码：(Java、C++) ####

Java

public class AddBinary {
        
    
    	public static void main(String[] args) {
        
    		// TODO Auto-generated method stub
    		String a = "11";
    		String b = "1";
    		System.out.println(addBinary(a,b));
    	}
    	
    	public static String addBinary(String a, String b) {
        
    		
    		StringBuilder  str = new StringBuilder();
    		boolean carry = false;
    		if(a.length() > b.length()) {
        
    			String temp = a;
    			a = b;
    			b = temp;
    		}
    		for(int i = a.length() - 1; i >= 0; i--) {
        
    			if(a.charAt(i) == '1' && b.charAt(i + b.length() - a.length()) == '1') {
        
    				str.append(carry == true ? '1' : '0');
    				carry = true;
    			}else if(a.charAt(i) == '1' || b.charAt(i + b.length() - a.length()) == '1') {
        
    				str.append(carry == true ? '0' : '1');
    			}else if(carry){
        
    				str.append('1');
    				carry = false;
    			}else {
        
    				str.append('0');
    			}
    		}
    		for(int i = b.length() - a.length() - 1; i >= 0; i--) {
        
    			if(carry && b.charAt(i) == '1') {
        
    				str.append('0');
    			}else if(carry || b.charAt(i) == 1) {
        
    				str.append('1');
    				carry = false;
    			}else {
        
    				str.append(b.charAt(i));
    			}
    		}
    		if(carry) {
        
    			str.append('1');
    		}
    		return str.reverse().toString();
        }
    }

**优化：**  
Java

public String addBinary(String a, String b) {
        
        int i = a.length() - 1, j = b.length() - 1, carry = 0;
        StringBuilder str = new StringBuilder();
        while (carry == 1 || i >= 0 || j >= 0) {
        
            if (i >= 0 && a.charAt(i--) == '1') {
        
                carry++;
            }
            if (j >= 0 && b.charAt(j--) == '1') {
        
                carry++;
            }
            str.append(carry % 2);
            carry /= 2;
        }
        return str.reverse().toString();
    }

C++

string addBinary(string a, string b) {
        
    	int i = a.size() - 1, j = b.size() - 1, carry = 0;
    	string str;
    	while (i >= 0 || j >= 0 || carry == 1)
    	{
        
    		if (i >= 0 && a[i--] == '1') {
        
    			carry++;
    		}
    		if (j >= 0 && b[j--] == '1') {
        
    			carry++;
    		}
    		str += carry % 2  + '0';
    		carry /= 2;
    	}
    	reverse(str.begin(), str.end());
    	return str;
    }

##### 运行结果： #####

![在这里插入图片描述][db263fe76a6e43fdb3f26c03d0d0afdc.png]

##### 复杂度分析： #####

*  **时间复杂度**： O ( n ) O(n) O(n)，n位字符串`a` 和 `b` 中长度最长的那个。
 *  **空间复杂度**： O ( 1 ) O(1) O(1)，除去答案所占用的空间，这里使用了常数个临时变量。

题目来源：[力扣。][Link 1]

##### 注：仅供学习参考， 如有不足，欢迎指正！ #####

[db263fe76a6e43fdb3f26c03d0d0afdc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/a0eee3e776c4441ab962dfa03bc4a675.png
[Link 1]: https://leetcode.cn/problems/add-binary/description/?orderBy=most_votes