[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——基本數據類型