Given two binary strings, return their sum (also a binary string).
For example,
a =
"11"
b =
"1"
Return
"100"
.
A:
就是用个StringBuffer , 来保存并计算
public class Solution { public String addBinary(String a, String b) { // make them backward StringBuffer bufA = new StringBuffer(a); StringBuffer bufB = new StringBuffer(b); StringBuffer bufC = new StringBuffer(); bufA.reverse(); bufB.reverse(); int m = a.length(), n = b.length(); int carry =0; for(int i=0;i<Math.max(m,n);i++){ int c =0,d=0; if(i<m) c=bufA.charAt(i)-'0'; if(i<n) d = bufB.charAt(i)-'0'; bufC.append( (c+d+carry)%2); carry = (c+d+carry)/2; } if(carry ==1) bufC.append(1); return bufC.reverse().toString(); } }
------------------------第二遍---------思路一样---------------
public class Solution { public String addBinary(String a, String b) { // make two string of the same length // assume a is longer if(a.length()<b.length()){ String tmp = b; b = a; a = tmp; } // NOW, str2 is shorter StringBuffer buf = new StringBuffer(b); for(int i =0;i<a.length()-b.length();i++){ buf.insert(0,'0'); } b = buf.toString(); // now a and b are of the same length; boolean carry = false; // first carry is zero StringBuffer result = new StringBuffer(); for(int i =a.length()-1;i>=0 ; i--){ boolean aa = a.charAt(i) == '1'; boolean bb = b.charAt(i) == '1'; if( logicalXOR(logicalXOR(aa,bb),carry) ){ result.insert(0,1); }else{ result.insert(0,0); } carry = aa&&bb || aa&&carry || bb&&carry; } if(carry){ result.insert(0,1); } return result.toString(); } private static boolean logicalXOR(boolean x, boolean y) { return ( ( x || y ) && ! ( x && y ) ); } }
Learned:
1: StringBuffer 有个函数,是setCharAt(int index, char ch);
2: 计算residue 可以直接用 a^b即可。 (第一次,是用了!(a^b)了, 哎
-----------------------3 rd Pass ----------------思路同上,更加简洁-----------------
public class Solution { public String addBinary(String a, String b) { StringBuffer buf = new StringBuffer(); int carry = 0; int m = a.length(); int n = b.length(); for (int i = 0; i < Math.max(m, n); i++) { int ai = (i >= m) ? 0 : a.charAt(m-1-i) - '0'; int bi = (i >= n) ? 0 : b.charAt(n-1-i) - '0'; int ci = (ai ^ bi) ^ carry; buf.insert(0, ci); carry = (ai + bi + carry) / 2; } if (carry == 1) buf.insert(0, '1'); return buf.toString(); } }
No comments:
Post a Comment