剑指 Offer II 002. 二进制加法

一、题目

剑指 Offer II 002. 二进制加法

给定两个 01 字符串 a 和 b ，请计算它们的和，并以二进制字符串的形式输出。
注：

输入为 非空 字符串且只包含数字 1 和 0。
字符串如果不是 “0” ，就都不含前导零。

示例 1:
输入: a = "11", b = "10"
输出: "101"

二、解题思路

• 正常加法运算，逢二进一是二进制的法则
• 进位的这个一，我们需要找个变量才存储它，才能在下一次的循环中获取
• 对于不等长的字符串，我们需要进行适当的优化与判断

题解参考

方法: 双指针 + 进位加法逻辑
(1)双指针, 让两个数的末位对齐, 两个指针 i, j均从各自字符串的末尾开始走。
(2)定义一个空字符串ret 来存放结果, 一个count来记录每位的进位值, 初始值设为0。
(3)计算当前位置的数时, 每趟都要记得更新count的值。
(4)循环结束时, 由于低位的数字字符先加到了结果字符串中, 最后还需要 reverse 一次, 让位置恢复正常。

三、代码

class Solution:
def addBinary(self, a: str, b: str) -> str:
ret = '' #字符串ret记录结果
count = 0 # count记录进位
i, j = len(a) - 1, len(b) - 1
while i >= 0 or j >= 0 or count:#对不等长的字符串的判断
if i >= 0:
count += ord(a[i]) - ord('0')
if j >= 0:
count += ord(b[j]) - ord('0')
# count为1，ret值追加1；count为0或2，ret值追加0；
ret += str(count % 2)
count //= 2 # 清除进位，置为0
i, j = i - 1, j - 1
return ret[::-1] # 从右边最低位开始记录的，所以要反转
if __name__ == '__main__':
a = '11'
b = '10'
solution = Solution()
print(solution.addBinary(a, b))

???? ord(一个长度为1的字符串)：返回其对应的的ASCII值，如ord('0')=48。
???? 用ord()函数是因为字符串不能直接相加减。
???? count也要判断，是因为两个二位数相加，结果可能为三位数。

四、相同题型

本题与主站 67 题相同：https://leetcode-cn.com/problems/add-binary/
leetcode 989 号算法题：数组形式的整数加法
leetcode 66 号算法题：加1
leetcode 415 号算法题：字符串相加
leetcode 67 号算法题：二进制求和
leetcode 2 号算法题：两数相加

最后

以上就是酷炫白开水为你收集整理的剑指 Offer II 002. 二进制加法的全部内容，希望文章能够帮你解决剑指 Offer II 002. 二进制加法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。