题目
Given two binary strings a
and b
, return their sum as a binary string.
思考
题外话:根据LeetCode premium的说法,这题是no.4最常被Facebook面试问到的题目
这题是二进制相加的问题
什么是二进制
二进制是一种计数系统,基于数字 0 和 1。与十进制每10进1不同,二进制每2进1
二进制:0 -> 1 -> 10 就对应着十进制:0 -> 1 -> 2
难点
在解决这道问题时,个人觉得难点在于如何进位,其中包括了前进一位时,当前位归零
,记录进位到下一位的运算
,在代码实现时都让我有点卡顿
解决
首先,对于两个二进制相加,肯定要从最末尾的一位开始,而两个数字长度未必相同
所以我们先初始化两个指针分别指向两个数字String a和 String b的末尾
int countA = a.length() - 1;
int countB = b.length() - 1;
然后我们用sum
和carry
分别记录当前位、下一位的情况
有这么些情况:
- sum = 0,那么向结果String res加入0,carry也为0;
- sum = 1, 那么 res.append(1), carry = 0;
- sum = 2, res.append(0), carry = 1;
- sum = 3, res.append(1), carry = 1;
以上就是进位逻辑
最后不要忘记将进位也加入结果,如果carry不是0,那就加入结果
然后逆向输出
代码
class Solution {
public String addBinary(String a, String b) {
StringBuilder res = new StringBuilder();
int countA = a.length() - 1;
int countB = b.length() - 1;
int carry = 0;
while(countA >= 0 || countB >= 0) {
int sum = carry;
if (countA >= 0) sum += a.charAt(countA--) - '0';
if (countB >= 0) sum += b.charAt(countB--) - '0';
carry = sum > 1 ? 1 : 0;
res.append(sum%2);
}
if (carry != 0) {res.append(carry);}
return res.reverse().toString();
}
}
总结
主要还是要熟悉String的操作,以及想到记录当前位和进位的逻辑。
标签:Binary,String,int,res,sum,countA,Add,carry,LeetCode From: https://www.cnblogs.com/zoexcode/p/17892275.html