【经典算法】LeetCode 67. 二进制求和(Java/C/Python3/Golang实现含注释说明,Easy)

本文涉及的产品
云解析 DNS,旗舰版 1个月
云解析DNS,个人版 1个月
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
简介: 【经典算法】LeetCode 67. 二进制求和(Java/C/Python3/Golang实现含注释说明,Easy)

题目描述

给定两个二进制字符串,返回它们的和(也表示为二进制字符串)。

输入为两个非空的二进制字符串,只包含字符 ‘0’ 或 ‘1’。

原题:LeetCode 67

思路及实现

方式一:模拟手工加法

思路

我们可以通过模拟手工加法的过程来解决这个问题。从两个二进制字符串的末尾开始,逐位相加,并处理可能出现的进位。如果两个字符串长度不同,则需要在较短的字符串前面补0,使其长度与较长的字符串相等。最后,将得到的二进制结果反转,即为所求的和。

代码实现

Java版本
public class Solution {
    public String addBinary(String a, String b) {
        StringBuilder sb = new StringBuilder();
        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 += a.charAt(i) - '0';
                i--;
            }
            if (j >= 0) {
                sum += b.charAt(j) - '0';
                j--;
            }
            sb.append(sum % 2); // 当前位的值
            carry = sum / 2; // 更新进位
        }
        // 反转字符串得到正确的结果
        return sb.reverse().toString();
    }
}

说明:

  • 使用StringBuilder来构建结果字符串,因为StringBuilderappend操作比String的拼接操作更高效。
  • 初始化进位carry为0。
  • 使用两个指针ij分别指向两个字符串的末尾,然后逐步向前遍历。
  • 如果两个字符串长度不同,较短的字符串的指针会先到达其字符串开头的前面,此时只需要将另一个字符串的对应位与进位相加即可。
  • 将计算得到的当前位的值加到StringBuilder中,并更新进位。
  • 最后,将StringBuilder反转,并转换为字符串返回。
C语言版本
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char* addBinary(char* a, char* b) {
    int lenA = strlen(a);
    int lenB = strlen(b);
    int carry = 0;
    int maxLength = lenA > lenB ? lenA : lenB;
    char* result = (char*)malloc(maxLength + 2); // 多分配一位用于进位和字符串结尾'\0'
    int i = lenA - 1;
    int j = lenB - 1;
    int index = 0;
    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[index++] = sum % 2 + '0';
        carry = sum / 2;
    }
    result[index] = '\0'; // 字符串结尾
    // 反转结果字符串
    for (int start = 0, end = index - 1; start < end; start++, end--) {
        char temp = result[start];
        result[start] = result[end];
        result[end] = temp;
    }
    return result;
}

说明:

  • 使用动态内存分配为结果字符串分配空间。
  • 其他部分与Java版本类似,只是C语言需要手动管理内存。
Python3版本
class Solution:
    def addBinary(self, a: str, b: str) -> str:
        carry = 0
        i, j = len(a) - 1, len(b) - 1
        result = []
        while i >= 0 or j >= 0 or carry:
            sum_val
            = carry
            if i >= 0:
                sum_val += int(a[i])
                i -= 1
            if j >= 0:
                sum_val += int(b[j])
                j -= 1
            result.append(str(sum_val % 2))
            carry = sum_val // 2
        return ''.join(reversed(result))

说明:

  • 使用列表result来存储每一位的结果,最后反转并拼接成字符串。
  • Python中的字符串是不可变的,因此使用列表来处理每一位的相加。
Golang版本
package main
import (
  "fmt"
  "strconv"
  "strings"
)
func addBinary(a string, b string) string {
  carry := 0
  i, j := len(a)-1, len(b)-1
  var result strings.Builder
  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.WriteByte(byte(sum%2 + '0'))
    carry = sum / 2
  }
  // 反转结果字符串
  resultBytes := result.String()
  for i, j := 0, len(resultBytes)-1; i < j; i, j = i+1, j-1 {
    resultBytes = strings.Replace(resultBytes, string(resultBytes[i])+string(resultBytes[j]), string(resultBytes[j])+string(resultBytes[i]), 1)
  }
  return resultBytes
}
func main() {
  a := "1010"
  b := "1011"
  fmt.Println(addBinary(a, b)) // 输出: 10101
}

说明:

  • 使用strings.Builder来构建结果字符串,它提供了高效的字符串拼接方法。
  • 反转结果字符串时,通过交换字符串中的字符来实现。

复杂度分析

  • 时间复杂度:O(max(m, n)),其中m和n分别是两个输入字符串的长度。我们最多遍历两个字符串中的所有字符一次。
  • 空间复杂度:O(max(m, n)),用于存储结果字符串。在最坏情况下,两个字符串都是全1,相加后的结果长度会增加一位。

方式二:使用内建函数

思路

代码实现

使用内建函数进行二进制加法在Java、C,Python3和Golang中也是可行的,但需要注意的是,不同的语言有不同的内建函数和语法来处理字符串和整数之间的转换,以及整数的二进制表示。以下是如何在这些语言中使用内建函数进行二进制加法的示例。

Java版本
public class Solution {
    public String addBinary(String a, String b) {
        int num1 = Integer.parseInt(a, 2); // 将二进制字符串转换为整数
        int num2 = Integer.parseInt(b, 2);
        int sum = num1 + num2;
        return Integer.toBinaryString(sum); // 将整数转换为二进制字符串
    }
}

注意:Java的Integer.parseIntInteger.toBinaryString方法分别用于将字符串解析为整数(给定基数)和将整数转换为二进制字符串。但请注意,如果二进制字符串表示的数字超出了int类型的范围(即大于Integer.MAX_VALUE或小于Integer.MIN_VALUE),则这种方法会失败。对于更大的数,可能需要使用BigInteger类。

C版本

在C中,没有直接的内建函数可以将二进制字符串转换为整数或将整数转换为二进制字符串,因此你需要手动实现这些功能。但是,你可以使用标准库中的函数来辅助处理字符串和整数。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
char* addBinary(char* a, char* b) {
    // 转换字符串到整数(手动实现,因为没有内建函数)
    int len_a = strlen(a);
    int len_b = strlen(b);
    int max_len = len_a > len_b ? len_a : len_b;
    int carry = 0;
    int sum = 0;
    int *result = (int *)malloc((max_len + 2) * sizeof(int)); // +2 for carry and null terminator
    result[max_len + 1] = '\0'; // Null terminator for the string
    // 从字符串的末尾开始相加,并处理进位
    for (int i = 0; i <= max_len; i++) {
        int digit_a = i < len_a ? a[len_a - i - 1] - '0' : 0;
        int digit_b = i < len_b ? b[len_b - i - 1] - '0' : 0;
        sum = digit_a + digit_b + carry;
        result[max_len - i] = sum % 2;
        carry = sum / 2;
    }
    // 如果最高位有进位,则需要添加一位
    if (carry > 0) {
        result = (int *)realloc(result, (max_len + 2 + 1) * sizeof(int));
        memmove(result + 1, result, (max_len + 2) * sizeof(int));
        result[0] = carry;
        result[max_len + 2] = '\0'; // Update null terminator position
    }
    // 将整数数组转换为字符串并返回
    char *binary_string = (char *)malloc((max_len + 2 + 1) * sizeof(char)); // +1 for null terminator
    for (int i = 0; i <= max_len + carry; i++) {
        binary_string[i] = result[max_len + carry - i] + '0';
    }
    binary_string[max_len + carry + 1] = '\0'; // Null terminator
    free(result); // 释放整数数组的内存
    return binary_string;
}

注意:这个C语言实现手动处理了二进制字符串到整数的转换、加法运算以及结果整数到字符串的转换。没有使用内建函数来直接执行这些操作,因为C标准库没有提供这样的功能。

Python3版本

在Python3中,我们可以将二进制字符串转换为整数,进行加法运算后再转回二进制字符串。这种方法简单直接,但可能不是最优的,因为涉及到整数的转换。

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        return bin(int(a, 2) + int(b, 2))[2:]

说明:

  • int(a, 2)将二进制字符串a转换为整数。
  • bin()函数将整数转换为二进制字符串,但前缀为0b,因此使用切片[2:]去掉前缀。
Golang版本
在Golang中,使用`strconv`包中的函数将二进制字符串转换为整数,并执行加法运算后,再将结果转换回二进制字符串,是一个简单且有效的方法。下面是完整的Golang代码示例:
package main
import (
  "fmt"
  "strconv"
)
func addBinary(a string, b string) string {
  // 将二进制字符串转换为整数
  num1, _ := strconv.ParseInt(a, 2, 64)
  num2, _ := strconv.ParseInt(b, 2, 64)
  // 执行加法运算
  sum := num1 + num2
  // 将整数转换回二进制字符串
  binarySum := strconv.FormatInt(sum, 2)
  return binarySum
}
func main() {
  a := "1010"
  b := "1011"
  fmt.Println(addBinary(a, b)) // 输出: 10101
}

注意:strconv.ParseInt函数用于将字符串解析为指定基数的整数,这里我们使用基数为2(二进制)。strconv.FormatInt函数用于将整数格式化为指定基数的字符串。

在这个例子中,我们假设输入的二进制字符串表示的数值不会超过int64类型的范围。如果输入的数值可能超出这个范围,你需要使用big.Int类型来处理大整数。但是,对于大多数常见的二进制字符串加法问题,使用int64类型通常是足够的。

使用内建函数的好处是代码简洁且易于理解,但缺点是当处理大数时可能会受到限制。如果你需要处理任意长度的二进制数,那么可能需要手动实现加法算法,就像前面C语言示例中所做的那样。然而,在Golang中,使用big.Int可以很容易地处理大整数,同时保持代码的可读性和简洁性。

复杂度分析

当分析内置函数用于二进制加法操作的复杂度时,我们需要区分时间复杂度和空间复杂度。时间复杂度关注的是算法执行所需的时间,而空间复杂度关注的是算法执行所需的额外空间(不包括输入数据本身所占用的空间)。

以下是以表格形式展示Java、C、Python 3和Golang中内置函数用于二进制加法操作的时间复杂度和空间复杂度分析:

语言 时间复杂度 空间复杂度 备注
Java O(n) O(1) int类型有固定位数(32位)
C O(n) O(1) 需要手动实现解析和转换
Python 3 O(n) O(n) 整数类型动态大小,字符串转换占用额外空间
Golang O(n) O(1) int64类型有固定位数(64位)

时间复杂度分析

  • 对于Java、C和Golang,解析二进制字符串为整数和将整数转换回二进制字符串的时间复杂度都是O(n),其中n是二进制字符串的长度。这是因为这两个操作都需要遍历字符串的每一位。
  • 整数加法的时间复杂度是O(1),因为这是一个固定时间的操作,不依赖于输入的大小(在固定位数的整数范围内)。

空间复杂度分析

  • 对于Java和Golang,空间复杂度是O(1)。这是因为这些语言中的整数类型是固定大小的,不需要额外的空间来存储中间结果。解析和转换操作通常只涉及对原有内存的修改,不需要分配额外的空间。
  • 对于C语言,虽然代码需要手动实现,但空间复杂度仍然是O(1),假设我们直接在原字符串上进行修改或者不使用额外的数据结构。
  • 对于Python 3,空间复杂度是O(n)。这是因为Python的字符串是不可变的,解析和转换操作通常会创建新的字符串对象,这些对象需要额外的空间来存储。此外,Python中的整数类型是动态大小的,但在这个特定场景下,整数的大小通常不会超过输入字符串的长度,因此整数本身不会显著增加空间复杂度。

需要注意的是,这里的空间复杂度分析是基于常见情况下的估计,并且假设没有其他额外的数据结构或变量被使用。在实际应用中,根据具体的实现方式和使用的数据结构,空间复杂度可能会有所不同。

总结

方式 优点 缺点 时间复杂度 空间复杂度
方式一 不依赖内建函数,灵活性强 代码量较大,实现相对复杂 O(max(m, n)) O(max(m, n))
方式二 代码简洁,易于理解 依赖内建函数,可能不是最优解 O(n) O(n) 或者O(1)

相似题目

相似题目 难度 链接
leetcode 369 给出数字在排序数组中的索引 简单 力扣:[力扣-369](https://leetcode-
相关文章
|
8天前
|
算法
刷算法Leetcode---9(二叉树篇Ⅲ)
刷算法Leetcode---9(二叉树篇Ⅲ)
11 3
|
26天前
|
算法 Java
[Java·算法·简单] LeetCode 283. 移动零
[Java·算法·简单] LeetCode 283. 移动零
22 2
|
26天前
|
算法 Java
[Java·算法·中等] LeetCode21. 合并两个有序链表
[Java·算法·中等] LeetCode21. 合并两个有序链表
18 2
|
29天前
|
存储 算法 调度
力扣中级算法(Python)
力扣中级算法(Python)
|
29天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
29天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
8天前
|
算法
Ngnix02 --- Ngnix的功能特性及常见功能,Ngnix常用的功能模块,有不同算法,根据不同算法进行转发,ip_hash、url_hash、fair,核心组成 ngnix二进制可执行文件
Ngnix02 --- Ngnix的功能特性及常见功能,Ngnix常用的功能模块,有不同算法,根据不同算法进行转发,ip_hash、url_hash、fair,核心组成 ngnix二进制可执行文件
|
1月前
|
算法
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
|
1月前
|
算法
【经典LeetCode算法题目专栏分类】【第11期】递归问题:字母大小写全排列、括号生成
【经典LeetCode算法题目专栏分类】【第11期】递归问题:字母大小写全排列、括号生成
|
1月前
|
算法
【经典LeetCode算法题目专栏分类】【第9期】深度优先搜索DFS与并查集:括号生成、岛屿问题、扫雷游戏
【经典LeetCode算法题目专栏分类】【第9期】深度优先搜索DFS与并查集:括号生成、岛屿问题、扫雷游戏