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)だよね。