NeetCode 150 [Bit Manipulation]:easy 1/2

NeetCodeのSolutionを書いていく

Single Number

問題概要

空ではない整数の配列numsが与えられる。
1つを除き、２度出現します。
1つしかない整数を返せ。

計算量：O(n)
メモリ：O(1)

メモ

Setにしても意味ないか。
重複していないものだけをメモリO(1)で取り出すには・・・？
複数回出現する場合は必ず2なのがポイントか？

setにして2回引いて、マイナスかければ行けるか。

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        sum_list = sum(nums)

        nums_set = set(nums)
        sum_set = sum(nums_set)

        return -(sum_list - sum_set - sum_set)

OKいけた！
あー。これだとメモリがO(1)じゃないからだめなんか。
わかりやすくていいと思ったけど。

やらせたかったのはこれらしい。XORビット演算で同じものは打ち消し合わせる。その結果１回だけのやつだけ残る。

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        res = 0
        for num in nums:
            res = num ^ res
        return res

Number of 1 Bits

問題概要

正の整数nが与えられます。
バイナリ表現にした時に1の数を返しなさい。

計算量：指定なし
メモリ：指定なし

メモ

単純にモジュロ演算と2で割るのを繰り返せばいいのでは？

class Solution:
    def hammingWeight(self, n: int) -> int:
        retval = 0
        while n != 0:
            retval += n % 2
            n //= 2
        return retval

行けた。けど何だこの問題。
簡単すぎというか。何を問うているのか・・・？

解法は以下。
なるほどビット演算を使うことを求めているんですね。
C++を使っている頃はよくビット演算していたけど、pythonを使うようになってめっきり。。。

class Solution:
    def hammingWeight(self, n: int) -> int:
        res = 0
        for i in range(32):
            if (1 << i) & n:
                res += 1
        return res