【LeetCode】就活に向けたコーディングテスト対策 #15

はじめに

こんばんは．
M1就活生がLeetCodeから，easy問題を中心にPythonを用いて解いていきます．

↓では，解いた問題のまとめを随時更新しています．
まとめ記事

問題

今回解いたのは，難易度easyから 問題67のAdd Binary です．
問題としては，2つの2進数からなる文字列aとbが与えられたとき，それらの合計を2進数文字列として返すというもの．
入力例と出力例は以下の通りです．

Example 1:

Input: a = "11", b = "1"
Output: "100"

Example 2:

Input: a = "1010", b = "1011"
Output: "10101"

書いたコード

書いたコードが以下になります．

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        i = len(a) - 1
        j = len(b) - 1
        result = ""
        carry = 0
        while any([i >= 0, j >= 0, carry != 0]):
            if i >= 0:
                carry += int(a[i])
                i -= 1
            if j >= 0:
                carry += int(b[j])
                j -= 1
            result = str(carry % 2) + result
            carry //= 2
        return result

2進数の合計は，桁上がりも意識する必要があるため，a，bそれぞれ，一番下の位から計算していきます．また，位が上がったときの桁も加算する必要があるため，桁上がり用の変数carryを0で初期化しておきます．carryにaとbをそれぞれ加算し，carryの値によってresultに結果を追加します．

carry = 0 → result = '0', carry = 0
carry = 1 → result = '1', carry = 0
carry = 2 → result = '0', carry = 1 # 桁が上がる
carry = 3 → result = '1', carry = 1 # 桁が上がる

この計算を，aの桁数，bの桁数，carry != 0まで続けることでバイナリ計算を行うことができます．

Pythonでもっと簡単に解くことができないか探してみたところ，int()を使って，2進数，8進数，16進数表記の文字列を数値に変換することができるということを知りました．

>>> int('10')
10
>>> int('10', 2)
2
>>> int('10', 8)
8
>>> int('10', 16)
16

これを使うと，2進数表記の文字列同士を計算することができます．

>>> int('11', 2) + int('1', 2)
4

しかし，結果は10進数の数値として返ってくるため，再び2進数に変換する必要があります．そこで組み込み関数bin()を使います．すると，このように簡単に2進数の計算を行うことができます．

>>> bin(int('11', 2) + int('1', 2))
'0b100'

2進数を表すプレフィックス（0b）は，スライスや書式化指定文字列などを使うと取り除くことができるため，今回の問題は以下のように1行のコードで記述することもできます．

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

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        return format(int(a, base = 2) + int(b, base = 2), 'b')

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        return f"{int(a, base = 2) + int(b, base = 2):b}"

おわりに

LeetCodeの問題には，高評価・低評価の仕様があります．比較的高評価の多い問題はやはり，アルゴリズム力が問われる良問が多い気がします．より良い問題に巡り会うため，できるだけこの評価も参考にして問題を選ぶことをオススメします．

今回書いたコードはGitHubにもあげておきます．

前回　次回