二進位求和

• 2022 年 2 月 15 日
• 筆記
• LeetCode刷題

二進位求和

題目鏈接

leetcode

題目描述

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

輸入為 非空 字元串且只包含數字 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自帶二進位轉十進位函數(因為整數類型是有限的，所以有問題)

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

第二種：分析 借鑒【列豎式】方法，末尾對齊，逐位相加，高位不夠補0。二進位是逢二進一。相同位數相加等於2，就進1，當前位變為0。

例如 1001 ， 10011，末尾對齊，從末位往回相加，1加1等於2，進一，當前位為變0，倒數第二位相加，1加0加1等於2，進一，當前位變為0，以此類推

    public static String addBinary(String a, String b) {
        StringBuilder ans = new StringBuilder();
        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;
        }
        //如果最高位不為0，則將最高位添加進計算結果中
        if(carry > 0) {
            ans.append('1');
        }
        //反轉
        ans.reverse();
        return ans.toString();
    }