二进制字符串相加问题解析
二进制字符串相加问题解析
问题描述
给定两个二进制字符串，返回它们的和（用十进制字符串表示）。输入为非空字符串且只包含数字 1 和 0，需要考虑大数问题。时间复杂度要求不超过 O(n^2)，其中 n 是二进制的最大长度。
解题思路
- 从右向左遍历：我们从两个二进制字符串的最右边（最低位）开始，逐位相加。
- 处理进位：在相加过程中，需要处理进位情况。
- 构建结果：将每一位的计算结果从右向左构建最终的二进制字符串。
- 转换为十进制：最后，将得到的二进制字符串转换为十进制。
代码实现
function addBinary(a, b) {
let result = "";
let carry = 0;
let i = a.length - 1;
let j = b.length - 1;
while (i >= 0 || j >= 0 || carry > 0) {
const sum = (i >= 0 ? parseInt(a[i]) : 0) + (j >= 0 ? parseInt(b[j]) : 0) + carry;
result = (sum % 2) + result;
carry = Math.floor(sum / 2);
i--;
j--;
}
return BigInt('0b' + result).toString();
}
Python 提供了内置的大整数支持，所以我们可以直接使用内置函数来处理二进制字符串。
def add_binary(a: str, b: str) -> str:
return bin(int(a, 2) + int(b, 2))[2:]
# 测试函数
def test(input_str: str) -> str:
a, b = input_str.split(',')
return str(int(add_binary(a, b), 2))
# 测试
print(test("101,110")) # 应输出 "11"
Go 解决方案
Go 没有内置的大整数类型，但标准库提供了 big.Int 用于处理大数。
package main
import (
"fmt"
"math/big"
"strings"
)
func addBinary(a, b string) string {
x, _ := new(big.Int).SetString(a, 2)
y, _ := new(big.Int).SetString(b, 2)
x.Add(x, y)
return x.Text(10)
}
func test(input string) string {
parts := strings.Split(input, ",")
return addBinary(parts[0], parts[1])
}
func main() {
fmt.Println(test("101,110")) // 应输出 "11"
}
C++ 解决方案
C++不直接支持任意精度整数，所以我们将实现一个按位加法的算法。
#include <iostream>
#include <string>
#include <algorithm>
class Solution {
public:
std::string addBinary(std::string a, std::string b) {
std::string result;
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[i--] - '0';
if (j >= 0) sum += b[j--] - '0';
result.push_back((sum % 2) + '0');
carry = sum / 2;
}
std::reverse(result.begin(), result.end());
return result;
}
};
std::string test(const std::string& input) {
size_t pos = input.find(',');
std::string a = input.substr(0, pos);
std::string b = input.substr(pos + 1);
Solution sol;
std::string binary_result = sol.addBinary(a, b);
// Convert binary to decimal
unsigned long long decimal_result = std::stoull(binary_result, nullptr, 2);
return std::to_string(decimal_result);
}
int main() {
std::cout << test("101,110") << std::endl; // 应输出 "11"
return 0;
}
Rust 解决方案
Rust 提供了 num-bigint crate 用于处理大整数，但为了保持一致性，我们这里使用标准库实现一个按位加法的算法。
fn add_binary(a: &str, b: &str) -> 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;
while i >= 0 || j >= 0 || carry > 0 {
let sum = carry
+ if i >= 0 { a.chars().nth(i as usize).unwrap() as i32 - '0' as i32 } else { 0 }
+ if j >= 0 { b.chars().nth(j as usize).unwrap() as i32 - '0' as i32 } else { 0 };
result.insert(0, (sum % 2 + '0' as i32) as u8 as char);
carry = sum / 2;
i -= 1;
j -= 1;
}
result
}
fn test(input: &str) -> String {
let parts: Vec<&str> = input.split(',').collect();
let binary_result = add_binary(parts[0], parts[1]);
u64::from_str_radix(&binary_result, 2).unwrap().to_string()
}
fn main() {
println!("{}", test("101,110")); // 应输出 "11"
}
代码解析(javascript)
-
初始化：
result：用于存储最终的二进制结果。carry：用于存储进位。i和j：分别指向两个输入字符串的最后一个字符。
-
主循环：
- 条件
i >= 0 || j >= 0 || carry > 0确保处理完所有位，包括可能的最后一个进位。 sum计算当前位的和，包括两个输入的对应位（如果存在）和进位。result = (sum % 2) + result将当前位的结果（0 或 1）添加到结果字符串的开头。carry = Math.floor(sum / 2)更新进位。
- 条件
-
结果转换：
- 使用
BigInt('0b' + result)将二进制字符串转换为 BigInt 类型。 .toString()将 BigInt 转换为十进制字符串。
- 使用
时间复杂度分析
- 时间复杂度：O(max(n, m))，其中 n 和 m 分别是两个输入字符串的长度。
- 空间复杂度：O(max(n, m))，用于存储结果字符串。
处理大数
使用 JavaScript 的 BigInt 类型来处理大数问题。BigInt 可以表示任意大的整数，不受 JavaScript 普通数字类型的限制。
结论
这个方案解决了二进制字符串相加的问题，同时也考虑到了大数的情况。通过逐位相加和处理进位，可以在线性时间内完成计算，满足时间复杂度的要求。使用 BigInt 确保了结果的准确性，即使对于非常大的二进制数也能正确处理。
原文地址：https://blog.csdn.net/weixin_40539956/article/details/142798968
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！