【問題描述】[簡單]

給你兩個二進制字符串，返回它們的和（用二進制表示）。輸入為 非空 字符串且只包含數字 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));} }

2. 模擬

時間復雜度：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. 位運算

class Solution:def addBinary(self, a, b) -> str:x, y = int(a, 2), int(b, 2)while y:answer = x ^ ycarry = (x & y) << 1x, y = answer, carryreturn 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的區別

運算速度

線性安全

總結

2.BigInteger

BigInteger API
BigInteger不是基本數據類型之一，它其實更像String,是Java里的一個類，然而它的初始化方式卻沒有String那么方便可以直接賦值，而是跟其他自定義的類一樣，要調用它的構造器進行初始化。這個類的取值范圍原則上是沒有上限的，取決于你的計算機的內存，它的構造器有以下幾種：

常用狗崽方法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（）這四種方法，它們的使用舉例如下：

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

總結

以上是生活随笔為你收集整理的[Leedcode][JAVA][第67题][二进制求和][位运算][字符串]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。