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

╰+攻爆jí腚メ 2022-01-20 11:01 133阅读 0赞

# 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;
        }
    }
    复制代码

若觉得本文章对你有用，欢迎用[爱发电][Link 1]资助。

[762. Prime Number of Set Bits in Binary Representation]: https://link.juejin.im?target=https%3A%2F%2Fleetcode.com%2Fproblems%2Fprime-number-of-set-bits-in-binary-representation%2F
[Link 1]: https://link.juejin.im?target=https%3A%2F%2Fafdian.net%2F%40skys215