iT邦幫忙

第 11 屆 iThome 鐵人賽

DAY 9
3
Software Development

從LeetCode學演算法系列 第 9

[Day 9] 從LeetCode學演算法 - 0067. Add Binary (Easy)

目標:
這題的目標在於講述簡單的字串操作方式,以及簡單的二進位的表示法。

原題:

Question:
Given two binary strings, return their sum (also a binary string).
The input strings are both non-empty and contain only characters 1 or 0.
Example 1:
Input: a = "11", b = "1"
Output: "100"
Example 2:
Input: a = "1010", b = "1011"
Output: "10101"

分析/解題:
題目給定兩個二進位字串,試求其和(同樣以二進位字串表達)。
在電腦的世界裡,本質上是由0和1所構成的,因為對它來說,
最容易的表達方式就是電路的開路和斷路兩種狀態。
如果大家忘記二進位的表示方式,可以從wiki的說明大概回憶一下XD
這裡只要知道要轉為10進位的話,就是由右至左從2⁰開始相乘相加就對了。
例: 1010 -> 0 * 2⁰ + 1 * 2¹ + 0 * 2² + 1 * 2³ = 0 + 2 + 0 + 8 = 10
每個位數之間是2倍,每滿2就要向左邊進一位。

如果是C/C++/Java等規範相對嚴格的語言的話,
以Java為例,其int變數型態一般是用32-bit來儲存並且含有正負號,
也就是它只可以接受範圍在**-2³¹~2³¹-**1之間的數字,超過這個範圍即會overflow(溢位),
這也是這個題目之所以會用字串表達的原因。
(不同的語言的int變數所涵蓋的範圍不一定相同)

Python就沒有這種限制,直譯器已經處理好很多事情了,
所以下面就會看到一些比較簡單(偷吃步)的做法。

對Java而言,我們既然擔心會溢位導致不能夠直接轉換,
那麼只好一位一位去做操作了。我們可以使用StringBuilder這個處理字串的類別,
從第0位開始將兩邊的數字相加,並且處理進位(carry)的部分。

對Java而言,字串(String)拆出來的每個單位叫字元(char),
使用String.charAt(i)函式,可以將index i的字元拆解出來。
拆出來的字元其實已經可以用數字的形態印出了,
但它是代表ASCII code表上的位置,而非真的數字,
要得到它實際的數字的話,由於'0'~'9'在表上是連續的,
我們可以減去'0'的位置48,即可得到實際的數字;
或者記不了的話,直接拿該字元去減掉'0',也可以得到相同的結果。
這樣的操作也適用於大小寫的英文字母上,請多留意。

那麼問題就簡單了: 只要是還有位數的狀況下,就取出字元減掉'0',
否則就當作是0(代表另一個字串比較長),最後比到兩邊長度都用完,
這時候StringBuilder應該沿路將所有位數從最低位組合到最高位了,
最後處理最高位有可能的進位後,只要再將其進行反轉(reverse)操作,
再轉為字串(toString)即可。

Java:

// Solution from lx223
public class Solution {
    public String addBinary(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int i = a.length() - 1, j = b.length() - 1, carry = 0;
        while (i >= 0 || j >= 0) {
            int sum = carry;
            if (j >= 0) sum += b.charAt(j--) - '0';
            if (i >= 0) sum += a.charAt(i--) - '0';
            sb.append(sum % 2);
            carry = sum / 2;
        }
        if (carry != 0) sb.append(carry);
        return sb.reverse().toString();
    }
}

Python的部分相對簡單的多(可以偷吃步XD),
只要將a跟b先轉成int,相加後再轉成二進位即可。
轉成int的作法是int(num, base)
num表示你的字串,base表示這段字串的進位方式
相加後轉成bin要特別注意Python的表達方式是以**’0b’**為開頭,
所以我們只保留index 2以後的部分。

Python:

class Solution:
    def addBinary(self, a: 'str', b: 'str') -> 'str':
        return bin(int(a, 2) + int(b, 2))[2:]

簡單吧!

面試實際可能會遇到的問題:
「時間複雜度?」( O(max(len(a), len(b))) )

「Python解是很簡單啦,但可以用一個一個比較的方法嗎?」
(請仿照Java的方式寫給他XD)
(補充: Python的ASCII和數字順序的互轉是 ord(c)跟 chr(a),
前者字元轉數字,後者數字轉字元)

「(Java)j++和++j有什麼不同?」
(++本身是代表將這個值增加1,
而擺在變數後面代表這整行執行完畢以後,才進行遞增
後者則代表先將自己本身增加1以後,才執行這整行的操作)

從LeetCode學演算法,我們下次見囉,掰~

下篇預告:
0070. Climbing Stairs (Easy)


上一篇
[Day 8] 從LeetCode學演算法 - 0053. Maximum Subarray (Easy)
下一篇
[Day 10] 從LeetCode學演算法 - 0070. Climbing Stairs (Easy)
系列文
從LeetCode學演算法30

尚未有邦友留言

立即登入留言