LeetCode之二进制求和（六十七）

目录

题目

解题

方法一、中规中矩法

题目

（原题链接：https://leetcode-cn.com/problems/add-binary/）

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

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

示例 1:

输入: a = "11", b = "1"
输出: "100"

示例 2:

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

提示：

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

解题

方法一、中规中矩法

分析：首先将字符串a和b进行补0对齐，然后按照我们对于二进制运算的计算顺序，从右侧（低位）开始相加计算，同时注意进位问题，思路很简单，下面直接看代码。

代码：

  

   

    

     

    
    

     

      class Solution {
     
    
   

    

     

    
    

     

      public:
     
    
   

    

     

    
    

     
 string addBinary(string a, string b) {
     
    
   

    

     

    
    

     
 int asize = a.size(), bsize = b.size();
     
    
   

    

     

    
    

     
		while (asize > bsize) //左侧补0
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     

      			b = '0' + b;
     
    
   

    

     

    
    

     

      			bsize++;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		while (asize < bsize) //左侧补0
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     

      			a = '0' + a;
     
    
   

    

     

    
    

     

      			asize++;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		int carry = 0;  //进位
     
    
   

    

     

    
    

     
		for (int i = asize - 1; i >= 0; i--)
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     
			int sum = a[i] - '0' + b[i] - '0' + carry;
     
    
   

    

     

    
    

     

      			a[i] = (sum) % 2+'0'; //本位数值
     
    
   

    

     

    
    

     

      			carry = sum / 2; //进位
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		if (carry > 0) { //最高位进位
     
    
   

    

     

    
    

     

      			a = '1' + a;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
		return a;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      };
     
    
  
 

时间复杂度：O（n+m）。

空间复杂度：O（1）。

执行结果：

文章来源: liuzhen.blog.csdn.net，作者：Data-Mining，版权归原作者所有，如需转载，请联系作者。

原文链接：liuzhen.blog.csdn.net/article/details/107095246