解法"/>
二进制求和 add binary 详解高效解法
给定两个二进制字符串,返回他们的和(用二进制表示)。
输入为非空字符串且只包含数字 1
和 0
。
示例 1:
输入: a = "11", b = "1" 输出: "100"
示例 2:
输入: a = "1010", b = "1011" 输出: "10101"
解法,利用倒序遍历求和,记住进位,如果发现遍历的某个串在该位没有值,那设置为0,不影响结果。最后不要忘记进位为1也要加入result结果集。请看code,两种方法,最后的方法非常精简。
public class AddBinary {//倒序遍历public static String addBinary(String a, String b) {int aIndex = a.length() - 1;//字符数组的索引int bIndex = b.length() - 1;String result = "";//结果字符串,通过新的结果+原来的结果=构成int carryBit = 0;//进位while (aIndex >= 0 || bIndex >= 0) {//三种情况,a,b的指针都还在if (aIndex >= 0 && bIndex >= 0) {//在ascii中,字符'0','1','2' ...是升序的,所以字符减去'0'就是差值,也就是int本身//当然这里也可以使用Integer.valueOf方法去转换char为intint tmpBit = a.charAt(aIndex) - '0' + b.charAt(bIndex) - '0' + carryBit;//上次和进位值,加上当前两个串某位值result = String.valueOf(tmpBit % 2) + result;//获得当前位求余2的结果carryBit = tmpBit / 2;//更新进位值,除以2aIndex--;bIndex--;} else if (aIndex >= 0) {//只有a stringint tmpBit = a.charAt(aIndex) - '0' + carryBit;result = String.valueOf(tmpBit % 2) + result;//获得当前位求余2的结果carryBit = tmpBit / 2;//更新进位值,除以2aIndex--;} else {//bLen>=0 ,只有b stringint tmpBit = b.charAt(bIndex) - '0' + carryBit;result = String.valueOf(tmpBit % 2) + result;//获得当前位求余2的结果carryBit = tmpBit / 2;//更新进位值,除以2bIndex--;}}if (carryBit == 1) {//必须考虑最后进位,如果是1需要加上result = "1" + result;}return result;}//方法的代码冗余的很多,可以精简提炼public static String addBinary2(String a, String b) {String result = "";//结果集int carryBit = 0;//进位int aIndex = a.length() - 1;//索引int bIndex = b.length() - 1;while (aIndex >= 0 || bIndex >= 0) {//每次遍历,都定义两个字符数组的位值,根据索引是否小于0判断,是不是使用0int tmpA = aIndex>=0? Integer.valueOf(""+a.charAt(aIndex)):0;int tmpB = bIndex>=0?Integer.valueOf(""+b.charAt(bIndex)):0;int tmpResult = tmpA+tmpB+carryBit;result = tmpResult%2+result;carryBit = tmpResult/2;aIndex--;//索引都减1bIndex--;}if(carryBit == 1){result = "1"+result;}return result;}public static void main(String[] args) {System.out.println(addBinary("11", "1"));}
}
更多推荐
二进制求和 add binary 详解高效解法
发布评论