TNotes.leetcode

Appearance

0762. 二进制表示中质数个计算置位【简单】

0762. 二进制表示中质数个计算置位【简单】 ​

1. 📝 题目描述 ​

  • 给你两个整数 left 和 right，在闭区间 [left, right] 范围内，统计并返回 计算置位位数为质数 的整数个数。
  • 计算置位位数 就是二进制表示中 1 的个数。
  • 例如， 21 的二进制表示 10101 有 3 个计算置位。

示例 1：

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

示例 2：

txt
输入：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

2. 🎯 s.1 - 位运算 + 质数判断 ​

js
/**
 * @param {number} left
 * @param {number} right
 * @return {number}
 */
var countPrimeSetBits = function (left, right) {
  // 判断一个数是否为质数
  const isPrime = (num) => {
    if (num < 2) return false
    if (num === 2) return true
    if (num % 2 === 0) return false

    for (let i = 3; i * i <= num; i += 2) {
      if (num % i === 0) return false
    }
    return true
  }

  // 计算一个数二进制表示中1的个数
  const countOnes = (num) => {
    let count = 0
    while (num > 0) {
      count += num & 1
      num >>= 1
    }
    return count
  }

  let result = 0
  for (let i = left; i <= right; i++) {
    const onesCount = countOnes(i)
    if (isPrime(onesCount)) {
      result++
    }
  }

  return result
}
  • 时间复杂度：O(n)，n 为输入区间的整数个数。
  • 空间复杂度：O(1)

3. 🎯 s.2 - 字符串操作 + 有效质数集合 ​

js
/**
 * @param {number} left
 * @param {number} right
 * @return {number}
 */
var countPrimeSetBits = function (left, right) {
  // 在32位整数范围内，1的个数最多为32，预先定义可能的质数集合
  const primes = new Set([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31])

  let result = 0
  for (let i = left; i <= right; i++) {
    // 使用内置函数计算1的个数
    const onesCount = i.toString(2).split('1').length - 1
    if (primes.has(onesCount)) {
      result++
    }
  }

  return result
}
js
/**
 * @param {number} left
 * @param {number} right
 * @return {number}
 */
var countPrimeSetBits = function (left, right) {
  const primes = new Set([2, 3, 5, 7, 11, 13, 17, 19])

  let result = 0
  for (let i = left; i <= right; i++) {
    const onesCount = i.toString(2).split('1').length - 1
    if (primes.has(onesCount)) {
      result++
    }
  }

  return result
}
  • 时间复杂度：O(n)，其中 n=right−left+1
  • 空间复杂度：O(1)
  • 知识点：
    • JS 中的数字类型，在参与位运算的时候，会自动地隐式转换为 32 位。
    • 相关笔记见 TNotes.javascript - 0129. Number 类型的取值范围【扩展】
  • 提示中提到的范围是 10^6，实际上 2^20 就大于 10^6 了，其实集合也没必要考虑到 32 位，只需要到 20 位就行了。因此使用 2.js 提交也能通过。

4. 🎯 s.3 - 使用 Brian Kernighan 算法优化计算置位位数 ​

js
/**
 * @param {number} left
 * @param {number} right
 * @return {number}
 */
var countPrimeSetBits = function (left, right) {
  // 预先定义可能的质数集合
  const primes = new Set([2, 3, 5, 7, 11, 13, 17, 19])

  let result = 0
  for (let i = left; i <= right; i++) {
    // 使用位运算计算1的个数
    const onesCount = bitCount(i)
    if (primes.has(onesCount)) {
      result++
    }
  }

  return result
}

// 计算一个数二进制表示中 1 的个数（Brian Kernighan算法）
const bitCount = (num) => {
  let count = 0
  while (num) {
    count++
    num &= num - 1 // 清除最低位的 1
  }
  return count
}
  • 时间复杂度：O(n)，其中 n=right−left+1
  • 空间复杂度：O(1)

Discussions