NeetCode 150 [Bit Manipulation]:easy 2/2

NeetCodeのSolutionを書いていく

Counting Bits

問題概要

整数nが与えられます。[0, n]の数値の間の数字を、全て2値にした場合の1の数を数えろ。
output[i]の形で、[0, n] を2値にした場合のそれぞれの1の個数を格納せよ。

例

Input: n=4
Output: [0,1,1,2,1]

メモ

とりあえず書き並べてみたけど、ピンとこないな。。。
なんか同じパターンを繰り返しているからDPかな・・・？
でも今までの感じだとビット演算をするはずだから、そんな方法があるはずか。

0 0
10 1
11 2

100 1
101 2
110 2
111 3

1000 1
1001 2
1010 2
1011 3
1100 2
1101 3
1110 3
1111 4

10000 1
10001 2
10010 2
10011 3
10100 2
10101 3
10110 3
10111 4
11000 2
11001 3
11010 3
11011 4
11100 3
11101 4
11110 4
11111 5

わからん。無理やりやるか。

class Solution:
    def countBits(self, n: int) -> List[int]:
        return [i.bit_count() for i in range(n + 1)]

行けたが。。。何も勉強にはなっていない。

回答はこんな感じ。

class Solution:
    def countBits(self, n: int) -> List[int]:
        res = [0] * (n + 1)
        for i in range(1, n + 1):
            num = i
            while num != 0:
                res[i] += 1
                num &= (num - 1)
        return res

何だ。DPか。
しかし回答をみてると、しっかりアルゴリズムの定式化をしないと解くのは辛いね。
紙必須。

Reverse Bits

問題概要

32bitの符号なし整数が与えられます。
ビット反転して結果を返しましょう。

例

Input: n = 00000000000000000000000000010101
Output: 2818572288 (10101000000000000000000000000000)

メモ

ビット反転して返すだけか。XORして返せばいいだけか？
おっと、ビット反転じゃなかった。1が立っている位置をビット位置で逆にするってことね。
単純にビットシフトして足してやってみるか。

class Solution:
    def reverseBits(self, n: int) -> int:
        bit_shift = 32
        result = 0
        for i in range(32):
            bit_shift -= 1
            bit = n % 2
            result += bit << bit_shift
            n //= 2
        return result

行けたー。

最適化の回答がすごい。

class Solution:
    def reverseBits(self, n: int) -> int:
        res = n
        res = (res >> 16) | (res << 16) & 0xFFFFFFFF
        res = ((res & 0xff00ff00) >> 8) | ((res & 0x00ff00ff) << 8)
        res = ((res & 0xf0f0f0f0) >> 4) | ((res & 0x0f0f0f0f) << 4)
        res = ((res & 0xcccccccc) >> 2) | ((res & 0x33333333) << 2)
        res = ((res & 0xaaaaaaaa) >> 1) | ((res & 0x55555555) << 1)
        return res & 0xFFFFFFFF

よくこんなの思いつくな。

Missing Number

問題概要

[0, n] の範囲に重複のないn個の整数が格納された配列が与えられた時に、配列に含まれない数字を一つ返せ。

計算時間 : O(n)
メモリ : O(1)

例

Input: nums = [1,2,3]
Output: 0

Input: nums = [0,2]
Output: 1

メモ

含まれない数を返す。ビット操作。
・・・
0~nの総計からnumsの総計を引けばいいのでは。
ビット操作感がないですが。

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        accum = 0
        for i in range(len(nums) + 1):
            accum += i
        return accum - sum(nums)

いけたー。
計算量はO(n)メモリはO(1)だよね。