LeetCode题练习与总结：二进制求和--67

本文主要是介绍LeetCode题练习与总结：二进制求和--67，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、题目描述

给你两个二进制字符串 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" ，就不含前导零

二、解题思路

1. 首先，我们需要理解二进制加法的基本原则。二进制加法类似于十进制加法，但是只有两个数字（0和1）参与计算。当两个位相加等于2时，我们需要进位，进位规则与十进制加法相同。
2. 为了处理不同长度的输入字符串，我们需要先对较短的字符串进行补全。我们可以通过在字符串前面添加'0'来实现，直到两个字符串长度相同。
3. 接下来，我们从两个字符串的末尾开始，逐位相加，并记录下每次相加是否产生进位。
4. 最后，如果最后还有进位未处理，需要将其作为结果字符串的首位。

三、具体代码

public class Solution {public String addBinary(String a, String b) {// 确保a是较长的字符串if (a.length() < b.length()) {String temp = a;a = b;b = temp;}// 对较短的字符串b进行补全int diff = a.length() - b.length();StringBuilder sb = new StringBuilder();for (int i = 0; i < diff; i++) {sb.append('0');}sb.append(b);// 翻转字符串，便于从末尾开始相加a = new StringBuilder(a).reverse().toString();sb.reverse();// 初始化结果字符串和进位StringBuilder result = new StringBuilder();int carry = 0;// 逐位相加for (int i = 0; i < a.length(); i++) {int sum = carry + (a.charAt(i) - '0') + (sb.charAt(i) - '0');carry = sum / 2;result.append(sum % 2);}// 处理最后的进位if (carry != 0) {result.append(carry);}// 翻转结果字符串，得到最终答案return result.reverse().toString();}
}

四、时间复杂度和空间复杂度

1. 时间复杂度

• 翻转字符串操作 a 和 sb 各需要 O(n) 的时间，其中 n 是字符串 a 的长度。
• 补全字符串 b 需要 O(n) 的时间。
• 逐位相加的过程需要 O(n) 的时间，因为它需要遍历两个字符串的所有字符。
• 最后，翻转结果字符串 result 需要 O(n) 的时间。
• 综上所述，主要的时间消耗在字符串的翻转和逐位相加上，这两个步骤都是 O(n) 的，因此整个函数的时间复杂度是 O(n)。

2. 空间复杂度

• 我们创建了一个新的 StringBuilder 对象 sb 来补全字符串 b，它的长度与 a 相同，即 O(n)。
• 我们还创建了另一个 StringBuilder 对象 result 来存储结果，最坏情况下，当两个字符串相加没有进位且长度相同时，结果的长度也是 O(n)。
• 其他变量和临时字符串翻转操作的空间消耗是常数级别的。
• 因此，整个函数的空间复杂度是 O(n)。

五、总结知识点

1. 字符串操作：

• length() 方法：用于获取字符串的长度。
• StringBuilder 类：用于创建可变的字符串序列，提供了多种方法来操作字符串，如 append()、reverse() 等。
• charAt() 方法：用于获取字符串中指定位置的字符。

2. 基本数据类型和运算：

• int 类型：用于存储整数，这里用于存储字符串中字符的数值和进位。
• 算术运算符：+ 用于加法运算，/ 用于整数除法，% 用于求余数，这些运算符在计算二进制和以及进位时使用。

3. 控制流：

• if 语句：用于条件判断，这里用于交换两个字符串的引用，确保 a 是较长的字符串。
• for 循环：用于重复执行代码块，这里用于补全较短的字符串 b 和逐位相加两个字符串。

4. 逻辑运算：

• 位运算：在二进制加法中，我们使用了位运算符 /（整除）和 %（取余）来处理进位和当前位的和。

5. 字符串翻转：

• 通过 StringBuilder 的 reverse() 方法，我们可以方便地翻转字符串。这对于从末尾开始逐位相加二进制字符串是非常有用的。

6. 变量和数据存储：

• 使用 StringBuilder 来构建结果字符串，而不是使用多个 + 操作符连接字符串，这是因为 StringBuilder 在内存中是连续存储的，可以有效地减少字符串连接时的内存分配和复制操作，提高性能。

7. 函数设计：

• 函数 addBinary 接收两个字符串参数 a 和 b，并返回它们的二进制和。
• 函数内部使用了局部变量来存储中间结果和状态，如 carry 用于记录进位，result 用于存储最终的二进制和。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。

这篇关于LeetCode题练习与总结：二进制求和--67的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---