|
| 1 | +packageeasy; |
| 2 | +/**67. Add Binary QuestionEditorial Solution My Submissions |
| 3 | +Total Accepted: 96848 |
| 4 | +Total Submissions: 337759 |
| 5 | +Difficulty: Easy |
| 6 | +Given two binary strings, return their sum (also a binary string). |
| 7 | +
|
| 8 | +For example, |
| 9 | +a = "11" |
| 10 | +b = "1" |
| 11 | +Return "100".*/ |
| 12 | +publicclassAddBinary { |
| 13 | +//then I turned to Discuss, this post is concise: https://discuss.leetcode.com/topic/13698/short-ac-solution-in-java-with-explanation |
| 14 | +//Tricks and things learned that could be learned: |
| 15 | +//1. use StringBuilder.reverse() function! Nice! |
| 16 | +//2. if a numeric number is represented/stored in String, how to get its value: use Character.getNumericValue(s.charAt(i)) |
| 17 | +//3. directly adding/subtracting chars will end up working with their ASCII numbers, e.g. chars[0] = 'a', chars[1] = 'b', then chars[0] + chars[1] will become 195 |
| 18 | + |
| 19 | +//my original lengthy but AC'ed solution |
| 20 | +publicStringaddBinary(Stringa,Stringb) { |
| 21 | +char[]longer = (a.length() >=b.length()) ?a.toCharArray() :b.toCharArray(); |
| 22 | +char[]shorter = (a.length() <b.length()) ?a.toCharArray() :b.toCharArray(); |
| 23 | +//at the maximum, the result length will be Math.max(a.length, b.length)+1; |
| 24 | +//let's use Math.max() as the length first, if the most signifant bits add up to a carry, then we'll add one more bit |
| 25 | +char[]result =newchar[longer.length]; |
| 26 | +booleancarry =false; |
| 27 | +inti =longer.length-1,j =shorter.length-1; |
| 28 | +System.out.println(Character.getNumericValue(longer[i]) +Character.getNumericValue(shorter[j])); |
| 29 | +System.out.println((int)longer[i] + (int)shorter[j]); |
| 30 | +System.out.println(longer[i] +shorter[j]); |
| 31 | +System.out.println('a' +'b'); |
| 32 | +for(;i >=0 ||j >=0;i--,j--){ |
| 33 | +if(j <0 &&i >=0){ |
| 34 | +if(carry){ |
| 35 | +if(Character.getNumericValue(longer[i])+1 ==2){ |
| 36 | +result[i] ='0'; |
| 37 | +carry =true; |
| 38 | + }else { |
| 39 | +result[i] ='1'; |
| 40 | +carry =false; |
| 41 | + } |
| 42 | + }else { |
| 43 | +for(intk =i;k >=0;k--){ |
| 44 | +result[k] =longer[k]; |
| 45 | + } |
| 46 | +returnnewString(result); |
| 47 | + } |
| 48 | + }elseif(Character.getNumericValue(longer[i]) +Character.getNumericValue(shorter[j]) ==2){ |
| 49 | +if(carry){ |
| 50 | +result[i] ='1'; |
| 51 | + }else { |
| 52 | +result[i] ='0'; |
| 53 | + } |
| 54 | +carry =true; |
| 55 | + }elseif(Character.getNumericValue(longer[i]) +Character.getNumericValue(shorter[j]) ==1){ |
| 56 | +if(carry){ |
| 57 | +result[i] ='0'; |
| 58 | +carry =true; |
| 59 | + }else { |
| 60 | +result[i] ='1'; |
| 61 | +carry =false; |
| 62 | + } |
| 63 | + }elseif(Character.getNumericValue(longer[i]) +Character.getNumericValue(shorter[j]) ==0){ |
| 64 | +if(carry){ |
| 65 | +result[i] ='1'; |
| 66 | + }else { |
| 67 | +result[i] ='0'; |
| 68 | + } |
| 69 | +carry =false; |
| 70 | + } |
| 71 | + } |
| 72 | +if(carry){ |
| 73 | +char[]newResult =newchar[longer.length+1]; |
| 74 | +newResult[0] ='1'; |
| 75 | +for(intk =0;k <result.length;k++){ |
| 76 | +newResult[k+1] =result[k]; |
| 77 | + } |
| 78 | +returnnewString(newResult); |
| 79 | + } |
| 80 | +returnnewString(result); |
| 81 | + } |
| 82 | + |
| 83 | +publicstaticvoidmain(String...args){ |
| 84 | +AddBinarytest =newAddBinary(); |
| 85 | +// String a = "0"; |
| 86 | +// String b = "0"; |
| 87 | +// String a = "11"; |
| 88 | +// String b = "1"; |
| 89 | +// String a = "100"; |
| 90 | +// String b = "110010"; |
| 91 | +Stringa ="101111"; |
| 92 | +Stringb ="10"; |
| 93 | +System.out.println(test.addBinary(a,b)); |
| 94 | + } |
| 95 | +} |