67. 二进制求和

Posted on Edited on In , ,
转载自Leet Code

题目描述

给你两个二进制字符串，返回它们的和（用二进制表示）。 输入为 非空 字符串且只包含数字 1 和 0。

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

示例 2: >输入: a = "1010", b = "1011" >输出: "10101"

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

我的代码

\(T(M,N) = O(max(M,N))\), \(S(M,N) = O(1)\)

{.line-numbers}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

class MySolution67 
{
    public String addBinary(String a, String b) 
    {
    	int i = a.length()-1; int j = b.length()-1;
    	StringBuilder sb = new StringBuilder();
    	
    	int add = 0;
    	for (; i>=0&&j>=0; i--,j--)
    	{
    		if (a.charAt(i)=='1'&&b.charAt(j)=='1') 
    		{
    			sb.append(add); add=1; 
    		}
    		else if (a.charAt(i)=='0'&&b.charAt(j)=='0')
    		{
    			sb.append(add); add = 0;
    		}
    		else
    		{
    			if (add==1)
    			{
    				sb.append(0); add = 1;
    			}
    			else
    			{
    				sb.append(1); add = 0;
    			}
    		}
    	}
    	while (i>=0)
    	{
    		if (add==1&&a.charAt(i)=='1')
    		{
    			sb.append(0); add = 1;
    		}
    		else if (add==0&&a.charAt(i)=='0')
    		{
    			sb.append(0); add = 0;
    		}
    		else
    		{
    			sb.append(1); add = 0;
    		}
    		i--;
    	}
    	while (j>=0)
    	{
    		if (add==1&&b.charAt(j)=='1')
    		{
    			sb.append(0); add = 1;
    		}
    		else if (add==0&&b.charAt(j)=='0')
    		{
    			sb.append(0); add = 0;
    		}
    		else
    		{
    			sb.append(1); add = 0;
    		}
    		j--;
    	}
    	if (add==1) sb.append(1);
    	return sb.reverse().toString();
    }
}

方法: 位运算模拟加法

\(T(M,N) = O(M+N+X·max(M,N))\), \(S(M,N) = O(M+N)\)

我们可以设计这样的算法来计算：

  • 把 a和 b 转换成整型数字 x和 y，在接下来的过程中，x 保存结果，y 保存进位。
  • 当进位不为 0 时
    • 计算当前 x 和 y 的无进位相加 (异或) 结果：answer = x ^ y
    • 计算当前 x 和 y 的进位：carry = (x & y) << 1
    • 完成本次循环，更新 x = answer，y = carry
  • 返回x 的二进制形式

为什么这个方法是可行的呢？ 在第一轮计算中，answer 的最后一位是 x 和 y 相加之后的结果， carry 的倒数第二位是 x 和 y 最后一位相加的进位。 接着每一轮中，由于 carry 是由 x 和 y 按位与并且左移得到的，那么最后会补零， 所以在下面计算的过程中后面的数位不受影响， 而每一轮都可以得到一个低i位的答案和它向低 i + 1 位的进位， 也就模拟了加法的过程。

时空复杂度

  • \(T(M,N) = O(M+N+X·max(M,N))\)，字符串转化成数字需要的时间代价为\(O(M+N)\)，计算的时间代价为\(O(max(M,N))\), \(X\) 为位运算所需的时间，因为这里用到了高精度计算，所以位运算的时间不一定为 \(O(1)\)； 递推式: \(T(N)=2·T(\frac N2)+O(M)\).
  • \(S(M,N) = O(M+N)\)，使用了x 和 y 来保存 a 和 b 的整数形式。
{.line-numbers}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution67 // a/b太大的时候不行
{
    public String addBinary(String a, String b) 
    {
    	long x = Long.parseLong(a, 2); long y = Long.parseLong(b, 2);
    	while (y!=0)
    	{
    		long ans = x ^ y;
    		long carry = (x & y) << 1;
    		x = ans; y = carry;
    	}
    	return Long.toString(x,2);
    }
}