#leetCode刷题纪实 Day29

给定两个整数 L 和 R ，找到闭区间 [L, R] 范围内，计算置位位数为质数的整数个数。

（注意，计算置位代表二进制表示中1的个数。例如 21 的二进制表示 10101 有 3 个计算置位。还有，1 不是质数。）

示例 1:

输入: L = 6, R = 10
输出: 4
解释:
6 -> 110 (2 个计算置位，2 是质数)
7 -> 111 (3 个计算置位，3 是质数)
9 -> 1001 (2 个计算置位，2 是质数)
10-> 1010 (2 个计算置位，2 是质数)
示例 2:

输入: L = 10, R = 15
输出: 5
解释:
10 -> 1010 (2 个计算置位, 2 是质数)
11 -> 1011 (3 个计算置位, 3 是质数)
12 -> 1100 (2 个计算置位, 2 是质数)
13 -> 1101 (3 个计算置位, 3 是质数)
14 -> 1110 (3 个计算置位, 3 是质数)
15 -> 1111 (4 个计算置位, 4 不是质数)
注意:

L, R 是 L <= R 且在 [1, 10^6] 中的整数。
R - L 的最大值为 10000。

小菜鸡的尝试：

读了题目，基本上只有最常规的想法：先转二进制过程中记录1的数量，再判断1的数量是否为质数。最后统计质数的数量。实现起来也不难。

 1 class Solution {
 2 public:
 3     int changeToBinAndCount(int num) {
 4         int remain = 0;
 5         string result;
 6         int count = 0;
 7         while (num != 0) {
 8             remain = num % 2;
 9             num = num / 2;
10             result = to_string(remain) + result;
11             if (remain == 1) count ++;
12         }
13         return count;
14     }
15     bool isPrime(int num) {
16         if (num == 2 || num == 3) return true;
17         if (num == 0 || num == 1) return false;
18         for (int i = 2; i <= sqrt(num); i ++) {
19             if (num % i == 0) return false;
20         }
21         return true;
22     }
23     int countPrimeSetBits(int L, int R) {
24         int count = 0;
25         for (int i = L; i <= R; i ++) {
26             if (isPrime(changeToBinAndCount(i))) count ++;
27         }
28         return count;
29     }
30 };

只不过，光荣地超时了

膜拜大佬代码：

 1 class Solution {
 2 public:
 3     int countPrimeSetBits(int L, int R) {
 4         int ans = 0;
 5         for(int i = L; i <= R; i ++) {
 6             int tmpNum = i, tmpCnt = 0;
　　　　　　　　　// 求二进制中1的个数
 7             while (tmpNum != 0) {
 8                 tmpNum &= tmpNum - 1;
 9                 tmpCnt ++;
10             }
11             if (isPrime(tmpCnt)) ans ++;
12         }
13         return ans;
14     }
15     bool isPrime(int num) {
16         if (num < 2) return false;
17         for (int i = 2; i * i <= num; i ++) {
18             if(num % i == 0) return false;
19         }
20         return true;
21     }
22 };