[Leedcode][JAVA][第67题][二进制求和][位运算][字符串]

小鱼儿 2023-02-20 04:46 63阅读 0赞

#### 【问题描述】\[简单\] ####

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

#### 【解答思路】 ####

###### 1. 朴素 ######

先将 aa 和 bb 转化成十进制数，求和后再转化为二进制数。利用 Python 和 Java 自带的高精度运算

class Solution { 
        public String addBinary(String a, String b) { 
            return Integer.toBinaryString(
                Integer.parseInt(a, 2) + Integer.parseInt(b, 2)
            );
        }
    }

![在这里插入图片描述][20200623110146876.png]

###### 2. 模拟 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]  
**时间复杂度：O(N) 空间复杂度：O(1)**

class Solution { 
        public String addBinary(String a, String b) { 
            StringBuffer ans = new StringBuffer();
    
            int n = Math.max(a.length(), b.length()), carry = 0;
            for (int i = 0; i < n; ++i) { 
                carry += i < a.length() ? (a.charAt(a.length() - 1 - i) - '0') : 0;
                carry += i < b.length() ? (b.charAt(b.length() - 1 - i) - '0') : 0;
                ans.append((char) (carry % 2 + '0'));
                carry /= 2;
            }
    
            if (carry > 0) { 
                ans.append('1');
            }
            ans.reverse();
    
            return ans.toString();
        }
    }

class Solution { 
        public String addBinary(String a, String b) { 
            int i = a.length() - 1, j = b.length() - 1;
            int carry = 0;
            StringBuilder res = new StringBuilder();
            while (i >= 0 || j >= 0 || carry > 0){ 
                int x = (i >= 0) ? a.charAt(i) - '0' : 0;
                int y = (j >= 0) ? b.charAt(j) - '0' : 0;
                int sum = x + y + carry;
                int curr = sum % 2;
                carry = sum / 2;
                res.append(curr);
                i--;
                j--;
            }
            return res.reverse().toString();
        }
    }

###### 3. 位运算 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][20200623110401198.png]

class Solution:
        def addBinary(self, a, b) -> str:
            x, y = int(a, 2), int(b, 2)
            while y:
                answer = x ^ y
                carry = (x & y) << 1
                x, y = answer, carry
            return bin(x)[2:]

**java版本位运算 但测试用例位数过长时会导致失败 所以java版本的位运算长答案错误 如果字符串超过 33 位，不能转化为 Integer 如果字符串超过 65 位，不能转化为 Long 如果字符串超过 500000001位，不能转化为 BigInteger**

public String addBinary(String a, String b) { 
           //long x= Long.parseLong(a, 2) ; return Long.toBinaryString(x);
           //BigInteger x= new BigInteger(a,10) ; 大整数是是Java里的一个类 位运算无法操作
            int x= Integer.parseInt(a, 2) ;//二进制转十进制 
            int y=Integer.parseInt(b, 2);
            int answer =0 ,carry = 0;
            while(y>0){ 
                answer = x^y;
                carry = (x&y)<<1;
                x=answer;
                y=carry;
            }
            return Integer.toBinaryString(x);//十进制转二进制 
    
        }

#### 【总结】 ####

###### 1.StringBuffer 和 StringBuilder 和String的区别 ######

**运算速度**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 3]  
**线性安全**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 4]  
**总结**  
![在这里插入图片描述][20200623111157781.png]

###### 2.BigInteger ######

[BigInteger API][]  
BigInteger不是基本数据类型之一，它其实更像String,是Java里的一个类，然而它的初始化方式却没有String那么方便可以直接赋值，而是跟其他自定义的类一样，要调用它的构造器进行初始化。这个类的取值范围原则上是没有上限的，取决于你的计算机的内存，它的构造器有以下几种：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 5]  
常用狗崽方法BigInger(String val)

BigInteger a=new BigInteger(“2222222222222222”);

**常用方法：**

BigInteger abs()  返回大整数的绝对值
    BigInteger add(BigInteger val) 返回两个大整数的和
    BigInteger and(BigInteger val)  返回两个大整数的按位与的结果
    BigInteger andNot(BigInteger val) 返回两个大整数与非的结果
    BigInteger divide(BigInteger val)  返回两个大整数的商
    double doubleValue()   返回大整数的double类型的值
    float floatValue()   返回大整数的float类型的值
    BigInteger gcd(BigInteger val)  返回大整数的最大公约数
    int intValue() 返回大整数的整型值
    long longValue() 返回大整数的long型值
    BigInteger max(BigInteger val) 返回两个大整数的最大者
    BigInteger min(BigInteger val) 返回两个大整数的最小者
    BigInteger mod(BigInteger val) 用当前大整数对val求模
    BigInteger multiply(BigInteger val) 返回两个大整数的积
    BigInteger negate() 返回当前大整数的相反数
    BigInteger not() 返回当前大整数的非
    BigInteger or(BigInteger val) 返回两个大整数的按位或
    BigInteger pow(int exponent) 返回当前大整数的exponent次方
    BigInteger remainder(BigInteger val) 返回当前大整数除以val的余数
    BigInteger leftShift(int n) 将当前大整数左移n位后返回
    BigInteger rightShift(int n) 将当前大整数右移n位后返回
    BigInteger subtract(BigInteger val)返回两个大整数相减的结果
    byte[] toByteArray(BigInteger val)将大整数转换成二进制反码保存在byte数组中
    String toString() 将当前大整数转换成十进制的字符串形式
    BigInteger xor(BigInteger val) 返回两个大整数的异或

既然不是基本数据类型，所以大数的加减乘除也不能使用+、-、\*、/这些运算符号，Java也没有对这些运算符号进行重定义，取而代之的是用一些方法来代替，比如add()、subtract（）、mutiply()、divide（）这四种方法，它们的使用举例如下：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 6]

###### 3. 一个没有遍历完 一个遍历完 使用三元运算符 carry进位思想 ######

参考链接：https://leetcode-cn.com/problems/add-binary/solution/er-jin-zhi-qiu-he-by-leetcode-solution/

参考链接：https://leetcode-cn.com/problems/add-binary/solution/guan-fang-ti-jie-fang-fa-er-xiang-jie-bu-shi-yong-/

参考链接：https://leetcode-cn.com/problems/add-binary/solution/java-lei-si-lian-biao-qiu-he-by-kelly2018/

参考链接：https://blog.csdn.net/qushaming/article/details/82971901

参考链接：https://www.jianshu.com/p/8b89ab19db84

[20200623110146876.png]: https://img-blog.csdnimg.cn/20200623110146876.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200623110241609.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200623105853522.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200623110323915.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[20200623110401198.png]: https://img-blog.csdnimg.cn/20200623110401198.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200623111029770.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/202006231112473.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[20200623111157781.png]: https://img-blog.csdnimg.cn/20200623111157781.png
[BigInteger API]: https://docs.oracle.com/javase/6/docs/api/java/math/BigInteger.html#BigInteger%28java.lang.String%29
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200623111746873.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/2020062311193075.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70