力扣00067.二进制求和

发表于 分类于 阅读次数： 本文字数： 1.8k 阅读时长 ≈ 7 分钟
二进制求和、位运算、数学、字符串、模拟、简单

题目描述

给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。

示例 1：

输入:a = “11”, b = “1”
输出：”100”

示例 2：

输入：a = “1010”, b = “1011”
输出：”10101”

提示：

  • $1 <= a.length, b.length <= 10^4$
  • a 和 b 仅由字符 ‘0’ 或 ‘1’ 组成
  • 字符串如果不是 “0” ，就不含前导零

解决方法

C++

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
class Solution {
public:
    string addBinary(string a, string b) {
        string result = "";
        int carry = 0;
        int i = a.length() - 1, j = b.length() - 1;
        while (i >= 0 || j >= 0) {
            int sum = carry;
            if (i >= 0) {
                sum += a[i] - '0';
                i--;
            }
            if (j >= 0) {
                sum += b[j] - '0';
                j--;
            }
            result = to_string(sum % 2) + result;
            carry = sum / 2;
        }
        if (carry) {
            result = "1" + result;
        }
        return result;
    }
};

结果

执行用时 : 4 ms, 击败 39.00% 使用 C++ 的用户

内存消耗 : 10.60 MB, 击败 9.70% 使用 C++ 的用户

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public String addBinary(String a, String b) {
        StringBuilder result = new StringBuilder();
        int carry = 0;
        int i = a.length() - 1, j = b.length() - 1;
        while (i >= 0 || j >= 0) {
            int sum = carry;
            if (i >= 0) {
                sum += a.charAt(i) - '0';
                i--;
            }
            if (j >= 0) {
                sum += b.charAt(j) - '0';
                j--;
            }
            result.insert(0, sum % 2);
            carry = sum / 2;
        }
        if (carry != 0) {
            result.insert(0, '1');
        }
        return result.toString();
    }
}

结果

执行用时 : 1 ms, 击败 99.49% 使用 Java 的用户

内存消耗 : 41.73 MB, 击败 22.66% 使用 Java 的用户

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def addBinary(self, a, b):
        """
        :type a: str
        :type b: str
        :rtype: str
        """
        result = ""
        carry = 0
        i, j = len(a) - 1, len(b) - 1
        while i >= 0 or j >= 0:
            sum = carry
            if i >= 0:
                sum += int(a[i])
                i -= 1
            if j >= 0:
                sum += int(b[j])
                j -= 1
            result = str(sum % 2) + result
            carry = sum // 2
        if carry:
            result = "1" + result
        return result

结果

执行用时 : 26 ms, 击败 23.78% 使用 Python 的用户

内存消耗 : 11.61 MB, 击败 25.55% 使用 Python 的用户

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def addBinary(self, a: str, b: str) -> str:
        result = ""
        carry = 0
        i, j = len(a) - 1, len(b) - 1
        while i >= 0 or j >= 0:
            sum = carry
            if i >= 0:
                sum += int(a[i])
                i -= 1
            if j >= 0:
                sum += int(b[j])
                j -= 1
            result = str(sum % 2) + result
            carry = sum // 2
        if carry:
            result = "1" + result
        return result

结果

执行用时 : 47 ms, 击败 13.36% 使用 Python3 的用户

内存消耗 : 16.46 MB, 击败 33.28% 使用 Python3 的用户

C

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
char* addBinary(char* a, char* b) {
    int lenA = strlen(a);
    int lenB = strlen(b);
    int lenResult = lenA > lenB ? lenA + 2 : lenB + 2;
    char* result = (char*)malloc(lenResult * sizeof(char));
    int carry = 0;
    int i = lenA - 1, j = lenB - 1;
    int k = 0;
    while (i >= 0 || j >= 0 || carry) {
        int sum = carry;
        if (i >= 0) {
            sum += a[i] - '0';
            i--;
        }
        if (j >= 0) {
            sum += b[j] - '0';
            j--;
        }
        result[k++] = sum % 2 + '0';
        carry = sum / 2;
    }
    for (int l = 0; l < k / 2; l++) {
        char temp = result[l];
        result[l] = result[k - l - 1];
        result[k - l - 1] = temp;
    }
    result[k] = '\0';
    return result;
}

结果

执行用时 : 2 ms, 击败 47.77% 使用 C 的用户

内存消耗 : 5.41 MB, 击败 93.22% 使用 C 的用户

C#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    public string AddBinary(string a, string b) {
        StringBuilder result = new StringBuilder();
        int carry = 0;
        int i = a.Length - 1, j = b.Length - 1;
        while (i >= 0 || j >= 0 || carry != 0) {
            int sum = carry;
            if (i >= 0) {
                sum += a[i] - '0';
                i--;
            }
            if (j >= 0) {
                sum += b[j] - '0';
                j--;
            }
            result.Insert(0, sum % 2);
            carry = sum / 2;
        }
        return result.ToString();
    }
}

结果

执行用时 : 52 ms, 击败 74.50% 使用 C# 的用户

内存消耗 : 40.38 MB, 击败 74.10% 使用 C# 的用户

JavaScript

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
/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
var addBinary = function(a, b) {
    let result = "";
    let carry = 0;
    let i = a.length - 1;
    let j = b.length - 1;
    while (i >= 0 || j >= 0 || carry !== 0) {
        let sum = carry;
        if (i >= 0) {
            sum += parseInt(a[i]);
            i--;
        }
        if (j >= 0) {
            sum += parseInt(b[j]);
            j--;
        }
        result = (sum % 2) + result;
        carry = Math.floor(sum / 2);
    }
    return result;
};

结果

执行用时 : 64 ms, 击败 59.82% 使用 JavaScript 的用户

内存消耗 : 51.32 MB, 击败 52.54% 使用 JavaScript 的用户

TypeScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function addBinary(a: string, b: string): string {
    let result = "";
    let carry = 0;
    let i = a.length - 1;
    let j = b.length - 1;
    while (i >= 0 || j >= 0 || carry !== 0) {
        let sum = carry;
        if (i >= 0) {
            sum += parseInt(a[i]);
            i--;
        }
        if (j >= 0) {
            sum += parseInt(b[j]);
            j--;
        }
        result = (sum % 2) + result;
        carry = Math.floor(sum / 2);
    }
    return result;
}

结果

执行用时 : 73 ms, 击败 30.34% 使用 TypeScript 的用户

内存消耗 : 52.49 MB, 击败 37.64% 使用 TypeScript 的用户

PHP

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
class Solution {
    
    /**
     * @param String $a
     * @param String $b
     * @return String
     */
    function addBinary($a, $b) {
        $result = "";
        $carry = 0;
        $i = strlen($a) - 1;
        $j = strlen($b) - 1;
        while ($i >= 0 || $j >= 0 || $carry !== 0) {
            $sum = $carry;
            if ($i >= 0) {
                $sum += intval($a[$i]);
                $i--;
            }
            if ($j >= 0) {
                $sum += intval($b[$j]);
                $j--;
            }
            $result = ($sum % 2) . $result;
            $carry = intval($sum / 2);
        }
        return $result;
    }
}

结果

执行用时 : 7 ms, 击败 67.86% 使用 PHP 的用户

内存消耗 : 20.33 MB, 击败 14.29% 使用 PHP 的用户

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
class Solution {
    func addBinary(_ a: String, _ b: String) -> String {
        var result = ""
        var carry = 0
        var i = a.count - 1
        var j = b.count - 1
        let aChars = Array(a)
        let bChars = Array(b)
        while i >= 0 || j >= 0 || carry != 0 {
            var sum = carry
            if i >= 0 {
                sum += Int(String(aChars[i])) ?? 0
                i -= 1
            }
            if j >= 0 {
                sum += Int(String(bChars[j])) ?? 0
                j -= 1
            }
            result = "\(sum % 2)" + result
            carry = sum / 2
        }
        return result
    }
}

结果

执行用时 : 8 ms, 击败 54.10% 使用 Swift 的用户

内存消耗 : 16.30 MB, 击败 24.59% 使用 Swift 的用户

Kotlin

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    fun addBinary(a: String, b: String): String {
        var result = ""
        var carry = 0
        var i = a.length - 1
        var j = b.length - 1
        while (i >= 0 || j >= 0 || carry != 0) {
            var sum = carry
            if (i >= 0) {
                sum += a[i] - '0'
                i--
            }
            if (j >= 0) {
                sum += b[j] - '0'
                j--
            }
            result = (sum % 2).toString() + result
            carry = sum / 2
        }
        return result
    }
}

结果

执行用时 : 178 ms, 击败 35.00% 使用 Kotlin 的用户

内存消耗 : 36.56 MB, 击败 30.00% 使用 Kotlin 的用户

Dart

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
  String addBinary(String a, String b) {
    StringBuffer result = StringBuffer();
    int carry = 0;
    int i = a.length - 1;
    int j = b.length - 1;
    while (i >= 0 || j >= 0 || carry != 0) {
      int sum = carry;
      if (i >= 0) {
        sum += int.parse(a[i]);
        i--;
      }
      if (j >= 0) {
        sum += int.parse(b[j]);
        j--;
      }
      result.write(sum % 2);
      carry = sum ~/ 2;
    }
    return result.toString().split('').reversed.join();
  }
}

结果

执行用时 : 328 ms, 击败 66.67% 使用 Dart 的用户

内存消耗 : 147.41 MB, 击败 66.67% 使用 Dart 的用户

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func addBinary(a string, b string) string {
    result := ""
    carry := 0
    i, j := len(a) - 1, len(b) - 1
    for i >= 0 || j >= 0 || carry != 0 {
        sum := carry
        if i >= 0 {
            sum += int(a[i] - '0')
            i--
        }
        if j >= 0 {
            sum += int(b[j] - '0')
            j--
        }
        result = strconv.Itoa(sum % 2) + result
        carry = sum / 2
    }
    return result
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 Go 的用户

内存消耗 : 3.58 MB, 击败 20.85% 使用 Go 的用户

Ruby

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# @param {String} a
# @param {String} b
# @return {String}
def add_binary(a, b)
    result = ""
    carry = 0
    i = a.length - 1
    j = b.length - 1
    while i >= 0 || j >= 0 || carry != 0
        sum = carry
        sum += a[i].to_i if i >= 0
        sum += b[j].to_i if j >= 0
        result = (sum % 2).to_s + result
        carry = sum / 2
        i -= 1
        j -= 1
    end
    result
end

结果

执行用时 : 60 ms, 击败 100.00% 使用 Ruby 的用户

内存消耗 : 207.01 MB, 击败 33.33% 使用 Ruby 的用户

Scala

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
object Solution {
  def addBinary(a: String, b: String): String = {
    val result = new StringBuilder()
    var carry = 0
    var i = a.length - 1
    var j = b.length - 1
    while (i >= 0 || j >= 0 || carry != 0) {
      var sum = carry
      if (i >= 0) {
        sum += a(i) - '0'
        i -= 1
      }
      if (j >= 0) {
        sum += b(j) - '0'
        j -= 1
      }
      result.insert(0, sum % 2)
      carry = sum / 2
    }
    result.toString()
  }
}

结果

执行用时 : 636 ms, 击败 -% 使用 Scala 的用户

内存消耗 : 57.54 MB, 击败 25.00% 使用 Scala 的用户

Rust

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
impl Solution {
    pub fn add_binary(a: String, b: String) -> String {
        let mut result = String::new();
        let mut carry = 0;
        let mut i = a.len() as i32 - 1;
        let mut j = b.len() as i32 - 1;
        let a_chars: Vec<char> = a.chars().collect();
        let b_chars: Vec<char> = b.chars().collect();
        while i >= 0 || j >= 0 || carry != 0 {
            let mut sum = carry;
            if i >= 0 {
                sum += a_chars[i as usize].to_digit(10).unwrap();
                i -= 1;
            }
            if j >= 0 {
                sum += b_chars[j as usize].to_digit(10).unwrap();
                j -= 1;
            }
            result.insert(0, std::char::from_digit(sum % 2, 10).unwrap());
            carry = sum / 2;
        }
        result
    }
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 Rust 的用户

内存消耗 : 2.09 MB, 击败 60.24% 使用 Rust 的用户

Racket

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Racket 的用户

内存消耗 : MB, 击败 % 使用 Racket 的用户

Erlang

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Erlang 的用户

内存消耗 : MB, 击败 % 使用 Erlang 的用户

Elixir

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Elixir 的用户

内存消耗 : MB, 击败 % 使用 Elixir 的用户