LeetCode刷题之旅（简单-16）： 二进制求和

LeetCode刷题之旅（简单-16）： 二进制求和

2019年6月15日

目录

​​题目：​​

​​解决方法1：暴力解释字符串运算​​

​​思路：​​

​​性能结果：​​

​​解决方法2：网友解法：判断每位字符是否一样​​

​​思路：​​

​​性能结果：​​

​​解决方法3：使用ASCII编码值运算，除以/整除2，获取当前位值/进位​​

​​思路：​​

​​性能结果：​​

​​小结：​​

题目：

解决方法1：暴力解释字符串运算

public class AddBinary { public static void main(String[] args){ String a = "100"; String b = "110010"; String result = addBinary(a, b); System.out.println("result="+result); } public static String addBinary(String a, String b) { if (a.equals("0") && b.equals("0")){ return "0"; }else if (a.equals("0")){ return b; }else if (b.equals("0")){ return a; } // 1.转为字符数组 char[] charsA = a.toCharArray(); char[] charsB = b.toCharArray(); int maxLength = (charsA.length > charsB.length)?(charsA.length):(charsB.length) +1; // 2.递归解决 String carryBit = ""; char[] result = new char[maxLength +1]; //预留一个元素空间 for (int i = 0;i < maxLength;i++){ String charA = "0"; String charB = "0"; // 3.逐个比较。数组未越界则赋值 if (charsA.length > i){ charA = String.valueOf(charsA[charsA.length-1 -i]); } if (charsB.length > i){ charB = String.valueOf(charsB[charsB.length-1 -i]); } // 4.递归解决 String sum = countAB(charA, charB,carryBit); if (sum != null){ switch (sum){ case "0": carryBit = "0";result[maxLength-i] = Character.valueOf('0'); break; case "1": carryBit = "0";result[maxLength-i] = Character.valueOf('1'); break; case "10":carryBit = "1";result[maxLength-i] = Character.valueOf('0'); break; case "11":carryBit = "1";result[maxLength-i] = Character.valueOf('1'); break; default: } } } // 5.比较最高位是否有进位 if (carryBit.equals("1")){ result[0] = '1'; } String string = new String(result); StringBuilder stringBuilder = new StringBuilder(); boolean flag = false; for (int i=0;i Character.valueOf('0')){ flag = true; } if (flag){ stringBuilder.append(result[i]); } } return stringBuilder.toString(); } // 位运算 public static String countAB(String a, String b, String carryBit) { String result = "0"; // 1.字符串余位判断（当有一个序列遍历结束） if (StringUtils.isEmpty(a)){ result = b; } if (StringUtils.isEmpty(b)){ result = a; } // 2.运算位判断 if ("1".equals(a) && "1".equals(b)){ result = "10"; } if ("0".equals(a)){ result = b; } if ("0".equals(b)){ result = a; } // 3.进位判断 if ("1".equals(carryBit)){ switch (result){ case "0": result = "1";break; case "1": result = "10";break; case "10": result = "11";break; default: } } return result; }}

思路：

一时半会没有想到更好的解决方法，于是按照对二进制运算的理解，前后提交了3次，最后才通过；自己也觉得解法不够好；算法解释：二进制运算简单，0,1，最多四种情况，对于进位，无非是多了一个判断而已；

性能结果：

解决方法2：网友解法：判断每位字符是否一样

class Solution { public String addBinary(String a, String b) { if (a.length() < b.length()) { String tmp = a; a = b; b = tmp; } char[] charsA = a.toCharArray(); int aLength = charsA.length - 1; int bLength = b.length() - 1; char carry = '0'; while (aLength >= 0) { char charsB = '0'; if (bLength >= 0) { charsB = b.charAt(bLength); } if (charsA[aLength] == charsB) { charsA[aLength] = carry; if (charsB != '0') { carry = '1'; }else { carry = '0'; } }else { if (carry == '0') { charsA[aLength] = '1'; }else { charsA[aLength] = '0'; carry = '1'; } } bLength --; aLength --; } return carry == '0'? String.valueOf(charsA):"1"+ String.valueOf(charsA); }}

思路：

不考虑二进制转十进制进行加法再转换回二进制的方法，这种方法有可能会出现溢出。先找出最长字符串，指定长的为 a，短的为 b。 将 a 转为字符数组，并以此进行加法，用 carry 记录进位。 遍历字符数组，进行加法运算。 注意 1：b 比 a 短，所以会先到达 0 坐标点，此时 b 跟 a 加的字符应当为 '0' 注意 2：如果 a 到达0坐标仍有进位，此时要把1加到第一位。

性能结果：

解决方法3：使用ASCII编码值运算，除以/整除2，获取当前位值/进位

public class BinaryAdd { public static void main(String [] args){ String a="101"; String b="100"; String result = binaryAdd(a, b); System.out.println("result"+result); } public static String binaryAdd(String a,String b){ int carry = 0; int i = a.length() -1; int j = b.length() -1; StringBuilder sb = new StringBuilder(); while (i >= 0 || j >= 0){ int sum = carry; if (i>=0){ sum += a.charAt(i--) - '0'; } if (j>=0){ sum += b.charAt(j--) - '0'; } sb.append(sum%2); carry = sum/2; } if (carry > 0){ sb.append(carry); } return sb.reverse().toString(); }}

思路：

将字符串的运算转为数字运算，非常巧妙啊！（整除解决当前位、除法解决进位）

性能结果：

小结：

差异化思维：这是解题的小秘诀，就是判断两个字符是否一致，一致情况下，如果任意为1或0，都将推出是否需要进位了；（差异化思维）一般写代码惊艳比较欠缺时，会以我这种菜鸟的顺序思维去解决问题，这样往往会费力很多；

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。