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