-
Notifications
You must be signed in to change notification settings - Fork 6
/
67_AddBinary.swift
49 lines (42 loc) · 1.73 KB
/
67_AddBinary.swift
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
//
// 67. 二进制求和
//
// 题目链接：https://leetcode-cn.com/problems/add-binary/
// 标签：字符串、数学
// 要点：按位逆序遍历，异或相加，重点思考进位（carry）🤔
// 时间复杂度：O(n)
// 空间复杂度：O(n)
// 注意：1. 转整数【Int(a, radix:2)】再相加的方案，无法处理溢出的情况
// 2. Swift 中 String 不支持直接下标随机访问，需要先转为数组
import Foundation
class Solution {
func addBinary(_ a: String, _ b: String) -> String {
let aChars = Array(a), bChars = Array(b)
var sum = 0, carry = 0, res = ""
var i = aChars.count - 1, j = bChars.count - 1
while i >= 0 || j >= 0 || carry > 0 {
let bitA: Int = {
if i < 0 { return 0 }
defer { i -= 1 }
return Int(String(aChars[i]))!
}()
let bitB: Int = {
if j < 0 { return 0 }
defer { j -= 1 }
return Int(String(bChars[j]))!
}()
sum = bitA ^ bitB ^ carry
carry = (bitA & bitB) | (carry & (bitA | bitB))
res = String(sum) + res
}
return res
}
}
// Tests
let s = Solution()
assert(s.addBinary("11", "1") == "100")
assert(s.addBinary("1010", "1011") == "10101")
let bigA = "10100000100100110110010000010101111011011001101110111111111101000000101111001110001111100001101"
let bigB = "110101001011101110001111100110001010100001101011101010000011011011001011101111001100000011011110011"
let bigExpectation = "110111101100010011000101110110100000011101000101011001000011011000001100011110011010010011000000000"
assert(s.addBinary(bigA, bigB) == bigExpectation)