二进制求和
难度:
标签:
题目描述
给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。
示例 1：
输入:a = "11", b = "1" 输出："100"
示例 2：
输入：a = "1010", b = "1011" 输出："10101"
提示：
1 <= a.length, b.length <= 104a和b仅由字符'0'或'1'组成- 字符串如果不是
"0"，就不含前导零
代码结果
运行时间: 44 ms, 内存: 15.2 MB
/*
* Solution for adding two binary strings using Java Streams
*
* 思路:
* 我们可以利用Stream流操作来简化对字符串的遍历。
* 我们将两个字符串的字符流转换为整数流, 然后使用累加器和carry进行计算。
* 最后, 将结果转换回字符串格式。
*/
import java.util.stream.Stream;
public class AddBinaryStream {
public String addBinary(String a, String b) {
int maxLength = Math.max(a.length(), b.length());
int carry = 0;
StringBuilder result = new StringBuilder();
for (int i = 0; i < maxLength; i++) {
int aBit = (i < a.length()) ? a.charAt(a.length() - 1 - i) - '0' : 0;
int bBit = (i < b.length()) ? b.charAt(b.length() - 1 - i) - '0' : 0;
int sum = aBit + bBit + carry;
result.append(sum % 2); // 结果位
carry = sum / 2; // 更新进位
}
if (carry != 0) result.append(carry); // 如果还有进位
return result.reverse().toString(); // 反转并返回结果
}
}
解释
方法:
这个题解采用了模拟二进制加法的方式来计算两个二进制字符串的和。从两个字符串的末尾开始，逐位相加，同时记录进位。最后将计算结果逆序，得到最终的二进制字符串。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
在处理二进制加法时，为什么需要在循环条件中包括`carry == 1`？
▷🦆
当其中一个二进制字符串较短时，代码是如何处理未对齐部分的二进制位的？
▷🦆
在最终结果中逆序前，为什么要将当前位的结果添加到答案字符串的开头而不是末尾？
▷🦆
代码中使用了`v1 = int(a[i]) if i >= 0 else 0`来获取当前位的值，这种方式是否有效避免了数组越界的错误？
▷相关问题
两数相加
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4] 输出：[7,0,8] 解释：342 + 465 = 807.
示例 2：
输入：l1 = [0], l2 = [0] 输出：[0]
示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] 输出：[8,9,9,9,0,0,0,1]
提示：
- 每个链表中的节点数在范围
[1, 100]内 0 <= Node.val <= 9- 题目数据保证列表表示的数字不含前导零
字符串相乘
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
示例 1:
输入: num1 = "2", num2 = "3" 输出: "6"
示例 2:
输入: num1 = "123", num2 = "456" 输出: "56088"
提示：
1 <= num1.length, num2.length <= 200num1和num2只能由数字组成。num1和num2都不包含任何前导零，除了数字0本身。
加一
给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
示例 1：
输入：digits = [1,2,3] 输出：[1,2,4] 解释：输入数组表示数字 123。
示例 2：
输入：digits = [4,3,2,1] 输出：[4,3,2,2] 解释：输入数组表示数字 4321。
示例 3：
输入：digits = [0] 输出：[1]
提示：
1 <= digits.length <= 1000 <= digits[i] <= 9
数组形式的整数加法
整数的 数组形式 num 是按照从左到右的顺序表示其数字的数组。
- 例如，对于
num = 1321，数组形式是[1,3,2,1]。
给定 num ，整数的 数组形式 ，和整数 k ，返回 整数 num + k 的 数组形式 。
示例 1：
输入：num = [1,2,0,0], k = 34 输出：[1,2,3,4] 解释：1200 + 34 = 1234
示例 2：
输入：num = [2,7,4], k = 181 输出：[4,5,5] 解释：274 + 181 = 455
示例 3：
输入：num = [2,1,5], k = 806 输出：[1,0,2,1] 解释：215 + 806 = 1021
提示：
1 <= num.length <= 1040 <= num[i] <= 9num不包含任何前导零，除了零本身1 <= k <= 104