LC 762. 二进制表示中质数个计算置位

题目描述

这是 LeetCode 上的 762. 二进制表示中质数个计算置位 ，难度为 简单。

给你两个整数 left 和 right，在闭区间 $[left, right]$ 范围内，统计并返回计算置位位数为质数的整数个数。

计算置位位数就是二进制表示中 $1$ 的个数。

例如， $21$ 的二进制表示 10101 有 $3$ 个计算置位。

示例 1：

1
2
3
4
5
6
7
8
9
10
输入：left = 6, right = 10

输出：4

解释：
6 -> 110 (2 个计算置位，2 是质数)
7 -> 111 (3 个计算置位，3 是质数)
9 -> 1001 (2 个计算置位，2 是质数)
10-> 1010 (2 个计算置位，2 是质数)
共计 4 个计算置位为质数的数字。

示例 2：
1
2
3
4
5
6
7
8
9
10
11
12
输入：left = 10, right = 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 不是质数)
共计 5 个计算置位为质数的数字。

提示：

  • $1 <= left <= right <= 10^6$
  • $0 <= right - left <= 10^4$

模拟 + lowbit

利用一个 int 的二进制表示不超过 $32$，我们可以先将 $32$ 以内的质数进行打表。

从前往后处理 $[left, right]$ 中的每个数 $x$，利用 lowbit 操作统计 $x$ 共有多少位 $1$，记为 $cnt$，若 $cnt$ 为质数，则对答案进行加一操作。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    static boolean[] hash = new boolean[40];
    static {
        int[] nums = new int[]{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
        for (int x : nums) hash[x] = true;
    }
    public int countPrimeSetBits(int left, int right) {
        int ans = 0;
        for (int i = left; i <= right; i++) {
            int x = i, cnt = 0;
            while (x != 0 && ++cnt >= 0) x -= (x & -x);
            if (hash[cnt]) ans++;
        }
        return ans;
    }
}

  • 时间复杂度：$O((right - left) * \log{right})$
  • 空间复杂度：$O(C)$

模拟 + 分治

枚举 $[left, right]$ 范围内的数总是不可避免，上述解法的复杂度取决于复杂度为 $O(\log{x})$ 的 lowbit 操作。

而比 lowbit 更加优秀的统计「二进制 $1$ 的数量」的做法最早在 (题解) 191. 位1的个数 讲过，采用「分治」思路对二进制进行成组统计，复杂度为 $O(\log{\log{x}})$。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    static boolean[] hash = new boolean[40];
    static {
        int[] nums = new int[]{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
        for (int x : nums) hash[x] = true;
    }
    public int countPrimeSetBits(int left, int right) {
        int ans = 0;
        for (int i = left; i <= right; i++) {
            int x = i;
            x = (x & 0x55555555) + ((x >>> 1)  & 0x55555555);
            x = (x & 0x33333333) + ((x >>> 2)  & 0x33333333);
            x = (x & 0x0f0f0f0f) + ((x >>> 4)  & 0x0f0f0f0f);
            x = (x & 0x00ff00ff) + ((x >>> 8)  & 0x00ff00ff);
            x = (x & 0x0000ffff) + ((x >>> 16) & 0x0000ffff);
            if (hash[x]) ans++;
        }
        return ans;
    }
}

  • 时间复杂度：$O((right - left) * \log{\log{right}})$
  • 空间复杂度：$O(C)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.762 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。