leetcode_rust/
add_binary.rs

1#![allow(dead_code)]
2
3pub fn add_binary(a: String, b: String) -> String {
4    let mut carry = false;
5    let a = a.into_bytes();
6    let b = b.into_bytes();
7    let mut i = a.len() as i32 - 1;
8    let mut j = b.len() as i32 - 1;
9    let mut sum = Vec::with_capacity(a.len().max(b.len()));
10    while i >= 0 && j >= 0 {
11        let ch = (a[i as usize], b[j as usize]);
12        if carry {
13            if ch.0 == b'1' && ch.1 == b'1' {
14                sum.push(b'1');
15                carry = true;
16            } else if ch.0 == b'0' && ch.1 == b'0' {
17                sum.push(b'1');
18                carry = false;
19            } else {
20                sum.push(b'0');
21                carry = true;
22            }
23        } else {
24            if ch.0 == b'1' && ch.1 == b'1' {
25                sum.push(b'0');
26                carry = true;
27            } else if ch.0 == b'0' && ch.1 == b'0' {
28                sum.push(b'0');
29                carry = false;
30            } else {
31                sum.push(b'1');
32                carry = false;
33            }
34        }
35        i -= 1;
36        j -= 1;
37    }
38    while i >= 0 {
39        let ch = a[i as usize];
40        if carry {
41            if ch == b'1' {
42                sum.push(b'0');
43                carry = true;
44            } else {
45                sum.push(b'1');
46                carry = false;
47            }
48        } else {
49            sum.push(ch);
50        }
51        i -= 1;
52    }
53
54    while j >= 0 {
55        let ch = b[j as usize];
56        if carry {
57            if ch == b'1' {
58                sum.push(b'0');
59                carry = true;
60            } else {
61                sum.push(b'1');
62                carry = false;
63            }
64        } else {
65            sum.push(ch);
66        }
67        j -= 1;
68    }
69
70    if carry {
71        sum.push(b'1');
72    }
73    sum.reverse();
74    unsafe { String::from_utf8_unchecked(sum) }
75}
76
77pub fn add_binary2(a: String, b: String) -> String {
78    let mut buf = Vec::with_capacity(usize::max(a.len(), b.len()) + 1);
79    let mut a = a.into_bytes();
80    let mut b = b.into_bytes();
81    let mut carry = 0;
82    while !(a.is_empty() && b.is_empty()) {
83        let mut sum = a.pop().map_or(b'0', |ch| ch) + b.pop().map_or(b'0', |ch| ch) - b'0' + carry;
84        if sum > b'1' {
85            sum -= 2;
86            carry = 1;
87        } else {
88            carry = 0;
89        }
90        buf.push(sum);
91    }
92    if carry > 0 {
93        buf.push(b'1')
94    }
95    buf.reverse();
96    unsafe { String::from_utf8_unchecked(buf) }
97}
98
99#[cfg(test)]
100mod tests {
101    use super::*;
102
103    #[test]
104    fn test1() {
105        let a = "11".to_string();
106        let b = "1".to_string();
107        assert_eq!(add_binary(a, b), "100".to_string());
108    }
109
110    #[test]
111    fn test2() {
112        let a = "11".to_string();
113        let b = "1".to_string();
114        assert_eq!(add_binary2(a, b), "100".to_string());
115
116        let a = "1010".to_string();
117        let b = "1011".to_string();
118        assert_eq!(add_binary2(a, b), "10101".to_string());
119    }
120}
leetcode_rust/add_binary.rs

leetcode_rust/
add_binary.rs
