67. Add Binary - Easy

前往題目

之前寫的文章

想法

• 從後面開始運算，但運算過程卡住

思路

1. 兩個指針都從後面開始
2. 每次循環都執行carry + aPointer + bPointer
3. 根據當前的sum計算新的carry
4. sum % 2加入到要回傳的String裡面
5. 移動指針
6. 當兩個指針都已經小於0的時候跳出
7. 如果還有carry就加上

Code

class Solution {
    public String addBinary(String a, String b) {
        StringBuilder res = new StringBuilder(); 
        int carry = 0;
        int aP = a.length() - 1, bP = b.length() - 1;

        // 直到a和b都全部走過
        while(aP >= 0 || bP >= 0) {
            int sum = carry;
            // 加上a和b pointer的值，但要小心出界
            sum += aP >= 0 ? a.charAt(aP) - '0' : 0;
            sum += bP >= 0 ? b.charAt(bP) - '0' : 0;

            // Compute new carry
            carry = sum > 1 ? 1 : 0;

            res.append(sum % 2);
            --aP;
            --bP;
        }
        
        // Add the last
        if (carry != 0) res.append(carry);
        return res.reverse().toString();
    }
}

2024/06/21

• 小錯誤，時間還是花得有點多