字节青训-二进制之和

问题描述

小U和小R喜欢探索二进制数字的奥秘。他们想找到一个方法，将两个二进制字符串相加并以十进制的形式呈现。这个过程需要注意的是，他们的二进制串可能非常长，所以常规的方法可能无法处理大数。小U和小R希望你帮助他们设计一个算法，该算法能在保证时间复杂度不超过O(n^2)的前提下，返回两个二进制字符串的十进制求和结果。

 

测试样例

样例1：

输入：binary1 = "101" ,binary2 = "110"
输出：'11'

样例2：

输入：binary1 = "111111" ,binary2 = "10100"
输出：'83'

样例3：

输入：binary1 = "111010101001001011" ,binary2 = "100010101001"
输出：'242420'

样例4：

输入：binary1 = "111010101001011" ,binary2 = "10010101001"
输出：'31220'

样例5：

输入：binary1 = "11" ,binary2 = "1"
输出：'4'

解题思路：

题目要求并不复杂，就是所谓的二进制转十进制相加，只不过需要考虑到长度的问题，其余地方我觉得没有需要注意的了

 整个逻辑下来就是用一个循环是遍历这个二进制字符串，并判断有没有进位，也就是说，循环条件为：如果两个字符串有一个还没遍历完或者有进位，都要继续计算下去，最后我们将结果重新转换成字符串返回即可，值得一提的是最终的结果需要进行反转，因为一开始处理是从字符串尾部开始的。

最终代码：

python：

def solution(a: str, b: str) -> str:result = []carry = 0  # 进位i, j = len(a) - 1, len(b) - 1while i >= 0 or j >= 0 or carry:sum_ = carry  # 先将进位加上if i >= 0:sum_ += int(a[i])  # 将字符转换为数字i -= 1if j >= 0:sum_ += int(b[j])  # 将字符转换为数字j -= 1carry = sum_ // 2  # 计算新的进位result.append(str(sum_ % 2))  # 结果取余，转换为字符result.reverse()  # 反转结果binary_result = ''.join(result)decimal_sum = int(binary_result, 2)return str(decimal_sum)# 测试代码
print(solution("101", "110") == "11")           # 二进制和 = "1011" = 11（十进制）
print(solution("111111", "10100") == "83")      # 二进制和 = "1010011" = 83（十进制）
print(solution("111010101001001011", "100010101001") == "242420")  # 二进制和 = "111011001101000100" = 242420（十进制）
print(solution("111010101001011", "10010101001") == "31220")       # 二进制和 = "111100110001100" = 31220（十进制）

c++：

 

#include <bits/stdc++.h>using namespace std;// 函数用于二进制字符串的加法
string addBinary(const string &a, const string &b) {string result;int carry = 0;  // 进位int i = a.size() - 1;int j = b.size() - 1;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--;}carry = sum / 2; // 计算新的进位result.push_back((sum % 2) + '0'); // 结果取余，转换为字符}reverse(result.begin(), result.end()); // 反转结果long long decimalSum = stoll(result, 0, 2);return to_string(decimalSum);
}// 主函数int main() {// You can add more test cases herestd::cout << (addBinary("101", "110") == "11") << std::endl;std::cout << (addBinary("111111", "10100") == "83") << std::endl;std::cout << (addBinary("111010101001001011", "100010101001") == "242420") << std::endl;std::cout << (addBinary("111010101001011", "10010101001") == "31220") << std::endl;return 0;
}

 

 最终也是成功通过啦