·
·
文章目录
  1. 题目介绍
  2. 复杂度
  3. 解题思路
    1. 函数
    2. 位运算
    3. String

Add Binary

题目介绍

LeetCode 67. Add Binary

复杂度

时间复杂度: O(Max(m, n)), 空间复杂度: O(Max(m, n))

解题思路

函数

使用内置函数,但是打印了下最大支持,理论上是超过 64 位 1 就不行了。

  • 转成十进制
  • 相加
  • 转成二进制输出
1
2
3
4
5
func addBinary(_ a: String, _ b: String) -> String {
let max = String(UInt64.max)
print("\(max) has \(max.count) digits.")
return String((UInt64(a, radix: 2) ?? 0) + (UInt64(b, radix: 2) ?? 0), radix: 2)
}

位运算

首先说明和上面问题一样,Int 64 的局限性,说下思路。

看到二进制的题目,要善用位运算。
相加用位运算分两步:

  • 按位异或 ^ :算出不进位每一位的相加值
  • 按位与 & 并左移以为 << :算出需要进位的二进制值
1
2
3
4
5
6
7
8
9
10
11
12
13
func addBinary(_ a: String, _ b: String) -> String {
var x = Int(a, radix: 2) ?? 0
var y = Int(b, radix: 2) ?? 0
var ans: Int = 0
var carry: Int = 0
while y != 0 {
ans = x ^ y
carry = (x & y) << 1
x = ans
y = carry
}
return String(ans, radix: 2)
}

String

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
class Solution {
func addBinary(_ a: String, _ b: String) -> String {
let a = Array(a)
let b = Array(b)
var ans = ""
var carry = 0
var i = a.count - 1
var j = b.count - 1
while i >= 0 || j >= 0 || carry > 0 {
if i >= 0 {
carry += Int(String(a[i]))!
i -= 1
}
if j >= 0 {
carry += Int(String(b[j]))!
j -= 1
}
ans = "\(carry % 2)" + ans
carry = carry / 2
}
return ans
}
/**
func addBinary(_ a: String, _ b: String) -> String {
let max = String(UInt64.max)
print("\(max) has \(max.count) digits.")
return String((UInt64(a, radix: 2) ?? 0) + (UInt64(b, radix: 2) ?? 0), radix: 2)
}
func addBinary(_ a: String, _ b: String) -> String {
var x = Int(a, radix: 2) ?? 0
var y = Int(b, radix: 2) ?? 0
var ans: Int = 0
var carry: Int = 0
while y != 0 {
ans = x ^ y
carry = (x & y) << 1
x = ans
y = carry
}
return String(ans, radix: 2)
}
*/
}

/**
看到二进制的题目,要善用位运算。
相加用位运算分两步:
- 按位异或 ^ :算出不进位每一位的相加值
- 按位与 & 并左移以为 << :算出需要进位的二进制值
*/
**版权声明**

Ivan’s Blog by Ivan Ye is licensed under a Creative Commons BY-NC-ND 4.0 International License.
叶帆创作并维护的叶帆的博客博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证

本文首发于Ivan’s Blog | 叶帆的博客博客( http://yeziahehe.com ),版权所有,侵权必究。

本文链接:http://yeziahehe.com/2020/03/07/AddBinary/

支持一下
扫一扫,支持yeziahehe
  • 微信扫一扫
  • 支付宝扫一扫