いいものをつくろう

CTOの日記

アルゴリズム

【アルゴリズム脳トレ】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が一個になる。(当初は桁くらい上がりで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: # 0から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を割り出せる

 

以上です

-アルゴリズム

Copyright© CTOの日記 , 2020 All Rights Reserved.