August 18, 2020
今まではpaizaのスキルチェックで試行錯誤してプログラミングの練習をしていました。ただpaizaのルール上ソースコードの公開ができず、他の人のコードを見ることが出来ません。
そこで見つけたのがLeetCodeなるGAFAなどで出題されているコーディングテストの問題が公開されているサービスを発見したので、挑戦してみました。
今回は挑戦した問題が「Add Binary」という問題でした。詳細は下記を参照してください。
2つの2進数を受け取り、合計を2進数で返すメソッドを作成すればいい問題です。
渡される値と返す値はこんな感じです。
Exapmple 1:
Input: a = "11", b = "1"
Output: "100"
Example 2:
Input: a = "1010", b = "1011"
Output: "10101"
こんなメソッドを作ればいいんでしょ?
def add_binary(a, b)
# ...
end
add_binary("1010", "1011")
#=> "10101"
「簡単そう…」と初めは思っていたんですが、気づいたら1時間以上もこの問題でハマってしまったので、復習を兼ねたアウトプットをしてきます。
def add_binary(a, b)
length = a.size > b.size ? a.size : b.size
result, carry = [], 0
1.upto(length) do |i|
sum = a[i * -1].to_i + b[i * -1].to_i
sum += carry
result.unshift((sum % 2).to_s)
carry = sum / 2
end
return result.unshift(carry.to_s).join unless carry.zero?
result.join
end
2進数足し算の筆算をやっているイメージです。
1 <- carry
1010 <- a
+ 10 <- b
------
1100 <- result
処理を順を追って文章化すると以下になります。
length
に代入します。
これは後でループ処理するのに利用します1
を運ぶ(carry)を初期化しておきます。upto
メソッドで 1 ~ length回ループを回します。
1.upto(5){ |i| print "#{i}, " }
#=> 1, 2, 3, 4, 5
こんな感じでupto
は繰り上がってくれるので、その数字をi * -1 => -i
で負の整数に変換します。
"1010"[i * -1] => "0"
"10"[i * -1] => "0"
これで、末尾から1桁づつ取り出して計算した結果をsum
に代入できるようになります。
carry
の値をsum
に追加する。これは前回のループでの値をcarry
で持ってきてもらうためです。
次に、 2
で余りを文字列に変換しunshift
で先頭からresult
に追加していきます。
carry = sum / 2
で繰り上がった部分を次のループに持ち越します。
1 <- ここをcarryで運ぶイメージ
1010
+ 10
------
1100
carry
の値が0
であれば、join
した結果を返し。carry
が0
意外であれば、unshift
で追加した結果をjoin
して返します。[Discuss]で色々コードを見てみようとした結果、ワンラインでのコーディングを見つけてしまいました。
def add_binary(a, b)
(a.to_i(2) + b.to_i(2)).to_s(2)
end
参考: One line Ruby solution | LeetCode
to_i(2)
やto_s(2)
で簡単に10進数 <-> 2進数
が出来てしまうみたいです。Rubyすごい
Onelineコードを見たときは、ちょっとびっくりしましたが、これが他者の解答を見れるいいところですね。
ただ、時間を掛けて試行錯誤した結果、使ったことがなかった・知らなかった方法を理解することが出来たのでいい感じです。
習得した内容
- upto / downto # downtoとか繰り返し処理めっちゃ豊富
- "abcd"[2] => c # 単に文字列でも配列のように取り出しが出来る
- 0.zero? # 0 == 0 と同じ