Leetcode PHP题解--D57 762. Prime Number of Set Bits in Binary Representation

D57 762. Prime Number of Set Bits in Binary Representation

题目链接

762. Prime Number of Set Bits in Binary Representation

题目分析

对给定范围内的每个整数，返回其二进制形式下，数字1出现的次数为质数的次数。

例如11111，1出现了5次，5是质数。
再如10111，1出现了4次，4不是质数。

思路

由于题目固定了范围为1~10^6，10^6次方为1千万。小于2^24。即最多只会出现24次1。

由于小于24的质数个数有限，我们直接写死24以内的质数。

对每一个数字，计算1出现的次数。再判断出现次数是否在这个质数数组内。

存在则符合题目要求的数字，否则不计入该数字。

最终代码

<?php
class Solution {
    /**
     * @param Integer $L
     * @param Integer $R
     * @return Integer
     */
    function countPrimeSetBits($L, $R) {
        $primes = [2,3,5,7,11,13,17,19,23];
        $nums = range($L,$R);
        $primeOnes = 0;
        foreach($nums as $num){
            $ones = array_filter(str_split(decbin($num)), function($val){
                return $val == '1';
            });
            if(in_array(count($ones),$primes)){
                $primeOnes++; 
            }
        }
        return $primeOnes;
    }
}
复制代码