概要
海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。
どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。
早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。
と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。
ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。
Python3で解いています。
前回
ゼロから始めるLeetCode Day53 「1365. How Many Numbers Are Smaller Than the Current Number」
今はTop 100 Liked QuestionsのMediumを優先的に解いています。
Easyは全て解いたので気になる方は目次の方へどうぞ。
Twitterやってます。
問題
1290. Convert Binary Number in a Linked List to Integer
難易度はEasy。
問題としては、単方向の連結リストheadが与えられます。
各ノードは0か1を値として持っており、それらを2進法の値として扱います。ここではそれらの二進法表記の値を10進法に直し、数字を返すアルゴリズムを設計してください、というものです。
Input: head = [1,0,1]
Output: 5
Explanation: (101) in base 2 = (5) in base 10
Input: head = [0]
Output: 0
Input: head = [1]
Output: 1
Input: head = [1,0,0,1,0,0,1,1,1,0,0,0,0,0,0]
Output: 18880
Input: head = [0,0]
Output: 0
解法
進数変換はちょいちょいあるネタな気がします。
最初は面食らうかもしれませんが、よくよく見てみるとワンパターンなことが多いので問題を解いて慣れてしまうことをお勧めします、
この問題での大事なのは、
- 連結リストの要素を全て網羅する
- 二進数から十進数へと変換する
という点なので、そこについて理解できていれば簡単かもしれません。
配列を用意し、配列へ追加、次の要素へ移動、というのをwhile文で書いてあげれば事足りそうです。
進数変換ですが、例えば、Pythonでは、
int('10',2)
といった形で書くと2進数を10進数に変換してくれるため、それを使えば変換自体は簡単です。
詳しく知りたい方は[公式ドキュメント]
(https://docs.python.org/ja/3/library/stdtypes.html?highlight=find)を参照することをお勧めします。
ここまでの流れをPythonで書いてみましょう。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getDecimalValue(self, head: ListNode) -> int:
ans = []
while head:
ans.append(str(head.val))
head = head.next
return int(''.join(ans),2)
# Runtime: 16 ms, faster than 99.88% of Python3 online submissions for Convert Binary Number in a Linked List to Integer.
# Memory Usage: 13.7 MB, less than 85.59% of Python3 online submissions for Convert Binary Number in a Linked List to Integer.
join関数は区切る要素を指定してあげると連結して文字列として返してくれる便利な関数です。
例えば、例で考えてみると、while文が終わった段階で、head = [1,0,1]を配列のansにstrで追加しているため、ans = ['1','0','1']となります。ここを連結するためにreturn以降の書き方をしてあげるとans['101',2]となるため、最終的にこれが10進数に変換されて返される、ということになります。
今回はここまで。お疲れ様でした。