【アルゴリズム脳トレ】leetcode medium 338 counting bits

こんにちは

今回の学びは

・落ち着いて法則性をみつけだそう

・full_adderでcarryが発生するかどうかで1bitsを割り出せる

問題は。。。

（時間配分は5分問題理解　10分検討 10分実装  20分振り返り　の一文45分構成)

まずは入出力をしっかりおさえましょう。

この問題の基礎問といっていいと思うのですが簡単だったので

記事にはしていないのですがnumber of 1bitsという問題をやりました

で

今回のcounting bitsはその数字を0から舐めて

数字ごとにnumber of 1bitsを出してよ。という欲張りな問題。

上の、Next challengeからも唯一のmedium問題のようです

なにか、

なにか法則性を見つけ出そうと

かいてみるわけですが中々たどりつきませんでしたね。ー

それでも

いくつか、見つかりました

1が増えるのを、直前の数字から割り出すことはできないものか？

・キャリオーバーした数 - 1　、1が増える

・一の位が1の時は必ず1増える

・1000とか桁繰り上がりのときは１が一個になる。（当初は桁くらい上がりで1増える、と考えていた）

という法則を実装することにした。桁繰り上がりの判断に以前、問題easy 371 sum of two integerにて、やったhalf_adderを利用することにした。

実装前後でこれは毎回書きましょう。timespace analysis (時間とスペースの分析）は　O(N * 32)

実際の実装はこちら

full_adderやgetNCarryは割愛、easy 371 sum of two integerを参考にしてほしい

def countBits(self, num: int) -> List[int]:
        counter = 0
        j = 1 # 桁が増えたかどうかの判定用
        p = 0
        ans = []
        for i in range(0, num+1):
            if i == 0:
                ans.append(0)
            else:
                keta = 2**j
                if i == keta:
                    j += 1
                    counter = 1
                else:
                    if i & 1 == 1: # ０から1へ、第一位がなった時
                        counter += 1
                    number_of_carryover = self.getNCarry(p, 1)
                    if number_of_carryover >= 2:
                        counter -= (number_of_carryover-1)

                ans.append(counter)
            p = i
        return ans

実装後です。timespace analysis (時間とスペースの分析）は　O(N)です

まとめ

・落ち着いて法則性をみつけだそう

・full_adderでcarryが発生するかどうかで1bitsを割り出せる

以上です