每日一道 LeetCode (15)：二進位求和

2020 年 8 月 12 日
筆記
leetcode

每天 3 分鐘，走上演算法的逆襲之路。

前文合集

每日一道 LeetCode 前文合集

程式碼倉庫

GitHub： //github.com/meteor1993/LeetCode

Gitee： //gitee.com/inwsy/LeetCode

題目：數組加一

題目來源：//leetcode-cn.com/problems/add-binary/

給你兩個二進位字元串，返回它們的和（用二進位表示）。

輸入為非空字元串且只包含數字 1 和 0。

示例 1:

輸入: a = "11", b = "1"
輸出: "100"

示例 2:

輸入: a = "1010", b = "1011"
輸出: "10101"

提示：

每個字元串僅由字元 ‘0’ 或 ‘1’ 組成。
1 <= a.length, b.length <= 10^4
字元串如果不是 “0” ，就都不含前導零。

解題過程

方案一：偷雞方法

每天做題就像一個開盲盒的過程，沒開始之前，永遠都不知道會遇到什麼樣的題目。

這道題我第一眼看過去，二進位加法？不會，我才不要自己去寫一個二進位加法出來， Java 給我們提供了現成的 math 函數包，是用來看的么？

果斷第一個想法是先把二進位轉成十進位，做完加法以後再轉回去做輸出。

我就是個小機靈鬼。

public String addBinary(String a, String b) {
    return decimalToBinary(binaryToDecimal(a).add(binaryToDecimal(b)));
}

// 定義二進位轉十進位
private BigInteger binaryToDecimal(String binarySource) {
    return new BigInteger(binarySource, 2);
}

// 定義十進位轉二進位
private String decimalToBinary(BigInteger decimalSource) {
    return decimalSource.toString(2);
}

程式碼上還可以精簡一點寫成一行，我是怕有同學看不懂，另外定義了兩個方法，比如：

public String addBinary(String a, String b) {
    return (new BigInteger(a, 2).add(new BigInteger(b, 2))).toString(2);
}

結果扔到 LeetCode 上去運行，直接給我報了個編譯錯誤。

這個意思應該是不支援 BigInteger() 函數，難道我在前面加個導包？

import java.math.BigInteger;

class Solution {
    public String addBinary(String a, String b) {
        return (new BigInteger(a, 2).add(new BigInteger(b, 2)).toString(2));
    }
}

果然添加了導包以後就正常了，就是這個執行耗時有點慘不忍睹。

果然每次取巧的方案最後消耗時長都是最坑的，還是老老實實的想辦法自己實現一下二進位加法吧。

方案二：二進位加法

二進位加法和十進位是一樣的，都是從低位開始往高位運算，只不過十進位是滿 10 進 1 ，而二進位是滿 2 進 1 。

我們接下來要做的就是模擬一下二進位的加法過程，從低位開始計算，並且實現滿 2 進 1 這個操作。

public String addBinary_1(String a, String b) {
    StringBuilder sb = new StringBuilder();
    // 定義進位
    int pre = 0;
    for (int i = a.length() - 1, j = b.length() - 1; i >= 0 || j >= 0; i--, j--) {
        int sum = pre;
        if (i >= 0) sum += a.charAt(i) - '0';
        if (j >= 0) sum += b.charAt(j) - '0';
        // 當前位添加至 sb
        sb.append(sum % 2);
        // 計算進位
        pre = sum / 2;
    }
    // 進位如果為 1 則添加到 sb 上
    if (pre == 1) sb.append('1');
    // 反轉字元串輸出
    return sb.reverse().toString();
}

上面這個演算法其中有一點需要注意，就是為什麼要做 a.charAt(i) - '0' 這樣一步操作，因為直接通過 a.charAt(i) 取出來的是當前字元的 ASCII 值， 0 的 ASCII 值是 48 ，而 1 的 ASCII 值是 49 ，用這兩個值都去減 '0' ，正好得到了我們需要的 1 或者 0 。

其餘的計算當前位是取模，計算進位是做除法，這兩個就不多說了，很常規的用法。

Tags: leetcode