600.不含连续1的非负整数

链接：600.不含连续1的非负整数
难度：Hard
标签：动态规划
简介：给定一个正整数 n，找出小于或等于 n 的非负整数中，其二进制表示不包含 连续的 1 的个数。

题解 1 - typescript

• 编辑时间：2021-09-11
• 执行用时：84ms
• 内存消耗：39.8MB
• 编程语言：typescript
• 解法介绍：[参考链接](https://leetcode-cn.com/problems/non-negative-integers-without-consecutive-ones/solution/bu-han-lian-xu-1de-fei-fu-zheng-shu-by-l-9l86/)。

function findIntegers(n: number): number {
  const dp = new Array(31).fill(0);
  dp[0] = dp[1] = 1;
  for (let i = 2; i < 31; ++i) dp[i] = dp[i - 1] + dp[i - 2];
  let pre = 0;
  let res = 0;
  for (let i = 29; i >= 0; --i) {
    let val = 1 << i;
    if ((n & val) !== 0) {
      res += dp[i + 1];
      if (pre === 1) break;
      pre = 1;
    } else pre = 0;
    if (i === 0) res++;
  }
  return res;
}

题解 2 - python

• 编辑时间：2024-08-05
• 执行用时：55ms
• 内存消耗：16.46MB
• 编程语言：python
• 解法介绍：数位dp。

N = len(bin(10 ** 9)) - 2
arr = [0] * (N + 1)
arr[0] = arr[1] = 1
tmp_sum = 1
for i in range(2, N + 1):
    arr[i] = tmp_sum
    tmp_sum += arr[i - 1]
class Solution:
    def findIntegers(self, num: int) -> int:
        if num == 0: return 1
        n = len(bin(num)) - 2
        res = sum(arr[:n])
        next_num = num
        if bin(next_num)[2:4] == '11':
            next_num = (1 << (n - 1)) + (1 << (n - 2)) - 1
        return sum(arr[:n]) + self.findIntegers(next_num - (1 << (n - 1)))