【leetcode】P67二进制求和

投机的解法

//给你两个二进制字符串，返回它们的和（用二进制表示）。 
//
// 输入为 非空 字符串且只包含数字 1 和 0。 
//
// 
//
// 示例 1: 
//
// 输入: a = "11", b = "1"
//输出: "100" 
//
// 示例 2: 
//
// 输入: a = "1010", b = "1011"
//输出: "10101" 
//
// 
//
// 提示： 
//
// 
// 每个字符串仅由字符 '0' 或 '1' 组成。 
// 1 <= a.length, b.length <= 10^4 
// 字符串如果不是 "0" ，就都不含前导零。 
// 
// Related Topics 数学 字符串 
// ? 508 ? 0

package leetcode.editor.cn;

//Java：二进制求和
public class P67AddBinary {
    public static void main(String[] args) {
        Solution solution = new P67AddBinary().new Solution();
        // TO TEST
        System.out.println(Integer.toBinaryString(8));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String addBinary(String a, String b) {
            int i = Integer.parseInt(b, 2);
            int j = Integer.parseInt(a, 2);
            return Integer.toBinaryString(i + j);
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}

当然，人家肯定不是想考这个，这个解法局限在于解析范围，超过32位Integer解析不了，超过64位Long解析不了
那么老老实实算吧，十进制怎么算，二进制就怎么算

//给你两个二进制字符串，返回它们的和（用二进制表示）。 
//
// 输入为 非空 字符串且只包含数字 1 和 0。 
//
// 
//
// 示例 1: 
//
// 输入: a = "11", b = "1"
//输出: "100" 
//
// 示例 2: 
//
// 输入: a = "1010", b = "1011"
//输出: "10101" 
//
// 
//
// 提示： 
//
// 
// 每个字符串仅由字符 '0' 或 '1' 组成。 
// 1 <= a.length, b.length <= 10^4 
// 字符串如果不是 "0" ，就都不含前导零。 
// 
// Related Topics 数学 字符串 
// ? 508 ? 0

package leetcode.editor.cn;

//Java：二进制求和
public class P67AddBinary {
    public static void main(String[] args) {
        Solution solution = new P67AddBinary().new Solution();
        // TO TEST
        String s = solution.addBinary("1010", "1011");
        System.out.println(s);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String addBinary(String a, String b) {
            if (a.length() < b.length()) {
                String temp = a;
                a = b;
                b = temp;
            }
            while (b.length() < a.length())
                b = "0" + b;
            String res = "";
            int carry = 0;
            for (int i = a.length() - 1; i > -1; i--) {
                int x = a.charAt(i) - '0';
                int y = b.charAt(i) - '0';
                int sum = x + y + carry;
                res = sum % 2 + res;
                carry = sum >= 2 ? 1 : 0;
            }
            return carry == 1 ? 1 + res : res;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}

但由于存在大量字符串拼接，频繁创建字符串对象，跑起来就很慢，内存占用也挺高，所以，用StringBuilder试试，于是有了下面这种看起来优雅点,实际跑起来也要快点(不多)的写法

//给你两个二进制字符串，返回它们的和（用二进制表示）。 
//
// 输入为 非空 字符串且只包含数字 1 和 0。 
//
// 
//
// 示例 1: 
//
// 输入: a = "11", b = "1"
//输出: "100" 
//
// 示例 2: 
//
// 输入: a = "1010", b = "1011"
//输出: "10101" 
//
// 
//
// 提示： 
//
// 
// 每个字符串仅由字符 '0' 或 '1' 组成。 
// 1 <= a.length, b.length <= 10^4 
// 字符串如果不是 "0" ，就都不含前导零。 
// 
// Related Topics 数学 字符串 
// ? 508 ? 0

package leetcode.editor.cn;

//Java：二进制求和
public class P67AddBinary {
    public static void main(String[] args) {
        Solution solution = new P67AddBinary().new Solution();
        // TO TEST
        String s = solution.addBinary("0", "0");
        System.out.println(s);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String addBinary(String a, String b) {
            int maxLen = a.length() > b.length() ? a.length() : b.length();
            StringBuilder res = new StringBuilder();
            int carry = 0;
            for (int i = 0; i < maxLen; i++) {
                //依次加a,b的当前位上的数
                carry += i < a.length() ? a.charAt(a.length() - 1 - i) - '0' : 0;
                carry += i < b.length() ? b.charAt(b.length() - 1 - i) - '0' : 0;
//                res.append(carry % 2);
//                转字符添加貌似比直接添加int数字快点
                res.append((char) (carry % 2 + '0'));
                carry = carry >= 2 ? 1 : 0;
            }
            if (carry != 0)
                res.append(1);
            res.reverse();
            return res.toString();
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}