首页 > itarticle > 算法笔记: 力扣#762 二进制表示中质数个计算置位

算法笔记: 力扣#762 二进制表示中质数个计算置位

admin 11月 12, 2020 0

问题描述

解法

分析

Python 实现

class :
    def countPrimeSetBits(self, L, R):
        """
        :type L: int
        :type R: int
        :rtype: int
        """
        prime_set = {2, 3, 5, 7, 11, 13, 17, 19}
        return sum(bin(n).count('1') in prime_set for n in range(L, R+1))

Java 实现

class  {
    public int countPrimeSetBits(int L, int R) {
        Set<Integer> prime_set = new HashSet<>(Arrays.asList(2, 3, 5, 7, 11, 13, 17, 19));
        int ans = 0;
        
        for(int n = L; n <= R; n++){
            if(prime_set.contains(Integer.bitCount(n))){
                ans ++;
            }
        }
        return ans;
    }
}

时间复杂度

O(N).

空间复杂度

O(1).

链接

762. Prime Number of Set Bits in Binary Representation
762. 二进制表示中质数个计算置位
 (English version) Algorithm Notes: Leetcode#762 Prime Number of Set Bits in Binary Representation