LeetCode】Add Binary(二进制求和)"/>
【LeetCode】Add Binary(二进制求和)
这道题是LeetCode里的第67道题。
题目描述:
给定两个二进制字符串,返回他们的和(用二进制表示)。
输入为非空字符串且只包含数字
1
和0
。示例 1:
输入: a = "11", b = "1" 输出: "100"
示例 2:
输入: a = "1010", b = "1011" 输出: "10101"
为了计算的方便我们把结果放入一个新的字符串里。
然后就是进位分析了,先设立一个进位标志位。最后我们每次取 a, b 串的最后的一个字符判断是否相等,具体流程如下:
然后在对剩下的字符进行简单的进位判断就行了。
解题代码:
class Solution {public String addBinary(String a, String b) {boolean carry = false;int aLen = a.length();int bLen = b.length();int minLen = aLen > bLen ? bLen : aLen;int difference = aLen > bLen ? aLen - bLen : bLen - aLen;StringBuilder c = new StringBuilder();int index;for(index = 1; index<=minLen; index++) {if(a.charAt(aLen - index) != b.charAt(bLen - index)) {if(carry) {c.insert(0, '0');//carry = true;}else {c.insert(0, '1');//carry = false;}}else if(a.charAt(aLen - index) == '0'){if(carry) {c.insert(0, '1');carry = false;}else {c.insert(0, '0');}}else {if(carry) {c.insert(0, '1');}else {c.insert(0, '0');carry = true;}}}if(a.length() > b.length()) {for(index = difference-1; index>=0; index--) {if(a.charAt(index) == '1') {if(carry) {c.insert(0, '0');//carry = true;}else {c.insert(0, '1');carry = false;}}else {if(carry) {c.insert(0, '1');carry = false;}else {c.insert(0, '0');}}}}else {for(index = difference-1; index>=0; index--) {if(b.charAt(index) == '1') {if(carry) {c.insert(0, '0');//carry = true;}else {c.insert(0, '1');carry = false;}}else {if(carry) {c.insert(0, '1');carry = false;}else {c.insert(0, '0');}}}}if(carry) {c.insert(0, '1');}return c.toString();}
}
提交结果:
个人总结:
另个种可行的思路是把二进制转换成十进制,然后相加,再转换回二进制,当然,有些语言可能会造成数据溢出。
更多推荐
【LeetCode】Add Binary(二进制求和)
发布评论