[LeetCode] 67. Add Binary java

2019-11-06 06:19:19

字体：大中小

来源：转载

供稿：网友

/**67. Add Binary * @param a * @param b * @returnString 字符串模拟二进制位相加运算 */ public String addBinary(String a, String b) { if (a == null || a.length() ==0) return b; if (b == null || b.length() == 0) return a; String ret = ""; char add = '0'; int i=a.length()-1, j=b.length()-1; while (i>=0 && j>=0) { int sum = (a.charAt(i)-'0') + (b.charAt(j)-'0') + (add - '0'); if (sum >= 2) { add = '1'; String s = (sum-2)==0? "0" :"1"; ret = s+ret; } else { add = '0'; ret = String.valueOf(sum)+ret; } i--; j--; } while(i>=0) { int sum = (a.charAt(i)-'0') + (add - '0'); if (sum >= 2) { add = '1'; String s = (sum-2)==0? "0" :"1"; ret = s+ret; }else { add = '0'; ret = String.valueOf(sum)+ret; } i--; } while(j>=0) { int sum = (b.charAt(j)-'0') + (add - '0'); if (sum >= 2) { add = '1'; String s = (sum-2)==0? "0" :"1"; ret = s+ret; }else { add = '0'; ret = String.valueOf(sum)+ret; } j--; } if (add != '0') { ret = String.valueOf(add) + ret; } return ret; }

用add存储每次相加时的进位记得最后循环结束后，要再次加一次add

改进：

public String addBinary1(String a, String b) { int m = a.length(); int n = b.length(); int carry = 0; String res = ""; int maxLen = Math.max(m, n); for (int i = 0; i < maxLen; i++) { int p = 0, q = 0; if (i < m) p = a.charAt(m - 1 - i) - '0'; else p = 0; if (i < n) q = b.charAt(n - 1 - i) - '0'; else q = 0; int tmp = p + q + carry; carry = tmp / 2; res += tmp % 2; } return (carry == 0) ? res : "1" + res; }

二进制加法都是从最低位（从右加到左）。所以对两个字符串要从最后一位开始加，如果遇见长度不一的情况，就把短的字符串高位补0. 每轮计算要加上进位，最后跳出循环后要坚持进位是否为1，以便更新结果。

上一篇：[LeetCode] 5. Longest Palindromic Substring java

下一篇：java——基本数据类型