概要
海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。
その対策としてLeetCodeなるサイトで対策を行うようだ。
早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイト。
せっかくだし人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。
前回
ゼロから始めるLeetCode Day12 「617. Merge Two Binary Trees」
基本的にeasyのacceptanceが高い順から解いていこうかと思います。
問題
難易度はMediumです。
最近はTop 100 Liked Questionsから優先的に選んでいるので良問が多いっぽいです。数学的な知識があるともちろん有利ですが、仮になくてもじっくり考えれば正解にたどり着くような問題が多くてとても面白いです。
自然数numが与えられます。0≦i≦numの範囲にある全ての数値iの2進数表現に含まれる1の数を計算し、配列として返します。
この問題も問題文だけだとパッと見ん？ってなりますね。例を見てみましょう。
Example 1:
Input: 2
Output: [0,1,1]
こちらの場合はnumとして2が与えられています。
[0,1,2]を2進数に変換すると[0,1,10]になり、これらのそれぞれの値に含まれる1の数をカウントすると011、配列に変換すると[0,1,1]となります。こちらの配列を最終的に返します。
Example 2:
Input: 5
Output: [0,1,1,2,1,2]
こちらの場合はnumとして5が与えられています。
[0,1,2,3,4,5]を2進数に変換すると[0,1,10,11,100,101]となり、これらの値に含まれる1の数をカウントすると011212となり、[0,1,1,2,1,2]となります。
解法
まず、返すためのリスト、ansを最初に用意し、1からnum+1までの値を繰り返すfor文を使って考えてみましょう。
それぞれの数字に関して2進数変換を行い、1のカウント数をリストに追加し、最終的に最初に用意したansを返します。
この問題で一番重要となるのはやはり2進数変換を行い、1の数をカウントするようなアルゴリズムでしょう。
ansのi番目を2で割り、その値をiを2で割った時の余りと足すとうまく変換されます。
何故なら、numの値が奇数であれば最後の桁が1となり右シフトを行うことで1を削除し、偶数の場合であれば必ず0となるため、右シフトを行っても同じ値の1となるためです。
こちらの例で考えてみると、例えばnumが4の場合、
ans[4/2]+(4%2)
となります。
この場合、ans[0,1,1,2]の2番目、すなわち1ですね。その1と(4%2)の余りである0が足され、4を2進数変換した際の'100'の1の数である1がリストへと追加されます。
私は以下のように書いてみました。
class Solution:
def countBits(self, num: int) -> List[int]:
ans = [0]
for i in range(1,num+1):
ans.append(ans[i//2] + (i%2))
return ans
# Runtime: 84 ms, faster than 72.90% of Python3 online submissions for Counting Bits.
# Memory Usage: 20.7 MB, less than 5.00% of Python3 online submissions for Counting Bits.
この問題は長い時間考え込んでしまいました。
もっとスパッと解法を思い付きたいですね。