不含连续1的非负整数

• 给定一个正整数 n，找出小于或等于 n 的非负整数中，其二进制表示不包含 连续的1 的个数。

示例

暴力超时

export const findIntegers_timeout = function (num) {
  const check = (num) => {
    let prev
    while (num > 0) {
      const next = num % 2
      num = (num - next) / 2
      if (prev * next === 1) return false
      prev = next
    }
    return true
  }
  let count = 0
  for (let i = 0; i <= num; i++) {
    if (check(i)) count++
  }
  return count
}

超时优化版

export const findIntegers_optimize = num => {
  const find = (i, sum, prev) => {
    if (sum > num) return 0
    if (1 << i > num) return 1
    if (prev) return find(i + 1, sum, false)
    return find(i + 1, sum, false) + find(i + 1, sum + (1 << i), true)
  }

  return find(0, 0, false)
}

动态规划[位运算]

从 numnum 的最高位开始考虑，对于第 ii 个位置遇到的 11 （从低位序号为 0 开始考虑），我们将答案加 f[i]f[i] ，对每个遇到的 00 ，我们不给答案加任何值。我们还要记录上一个位置的数值为多少，一旦我们发现连续的 1 ，我们将第二个 1 变成 0 的影响考虑后即停止遍历。如果我们没有遇到连续的 1 ，我们一直遍历到最低位并将最终答案加 1 ，表示 numnum 也是合法数字，因为上述过程并没有考虑 numnum 进去

F['0'] = 1
F['10'] = 2
F['100'] = 3
F['1000'] = 5
F['10000] = 8
F[n] = F[n - 1] + F[n - 2]

export const findIntegers = num => {
  const dp = new Array(32).fill(0)
  dp[0] = 1
  dp[1] = 2

  for (let i = 2; i < dp.length; i++) dp[i] = dp[i - 1] + dp[i - 2]

  let m = 30, sum = 0, prev_bit = 0

  while (m >= 0) {
    if ((num & (1 << m)) !== 0) {
      sum += dp[m]
      if (prev_bit === 1) {
        sum--
        break
      }
      prev_bit = 1
    } else prev_bit = 0
    
    m--
  }

  return sum + 1
}

findIntegers

console结果可能不准确，按F12打开控制台查看

LeetCode题解 (opens new window)