What is the main pattern to solve the Non-negative Integers without Consecutive Ones problem?

The main pattern involves dynamic programming with state transitions, specifically utilizing a Fibonacci-like sequence to count valid binary numbers.

How do I optimize the solution for large values of n?

To optimize for large n, use bit manipulation and dynamic programming to track valid numbers bit by bit, reducing the problem to O(log n) time complexity.

What is the time complexity of solving this problem?

The time complexity is O(log n), where n is the input number, as the solution processes the binary representation of n.

Can I solve this problem using brute force?

While brute force can work for small inputs, it is inefficient for large values of n. A dynamic programming approach is necessary for optimal performance.

What is the relationship between Fibonacci numbers and this problem?

The number of valid numbers follows a Fibonacci-like sequence, where the count of valid numbers for k bits is derived from the counts for k-1 and k-2 bits.

#600

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

不含连续1的非负整数

给定一个正整数 n ，请你统计在 [0, n] 范围的非负整数中，有多少个整数的二进制表示中不存在连续的 1 。示例 1: 输入: n = 5 输出: 5 解释: 下面列出范围在 [0, 5] 的非负整数与其对应的二进制表示： 0 : 0 1 : 1 2 : 10 3 : 11 4 : 100 …

动态规划

题目描述

给定一个正整数 n ，请你统计在 [0, n] 范围的非负整数中，有多少个整数的二进制表示中不存在 连续的 1 。

示例 1:

输入: n = 5
输出: 5
解释: 
下面列出范围在 [0, 5] 的非负整数与其对应的二进制表示：
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
其中，只有整数 3 违反规则（有两个连续的 1 ），其他 5 个满足规则。

示例 2:

输入: n = 1
输出: 2

示例 3:

输入: n = 2
输出: 3

提示:

1 <= n <= 10⁹

lightbulb

解题思路

方法一：数位 DP

这道题实际上是求在给定区间 $[l,..r]$ 中，数字的二进制表示不包含连续的 $1$ 的个数。个数与数的位数以及每个二进制位上的数字有关。我们可以用数位 DP 的思路来解决这道题。数位 DP 中，数的大小对复杂度的影响很小。

对于区间 $[l,..r]$ 问题，我们一般会将其转化为 $[0,..r]$ 然后再减去 $[0,..l - 1]$ 的问题，即：

ans = \sum_{i=0}^{r} ans_i - \sum_{i=0}^{l-1} ans_i

不过对于本题而言，我们只需要求出区间 $[0,..r]$ 的值即可。

这里我们用记忆化搜索来实现数位 DP。基本步骤如下：

我们首先获取数字 $n$ 的二进制长度，记为 $m$ 。然后根据题目信息，我们设计函数 $\textit{dfs}(i, \textit{pre}, \textit{limit})$ ，其中：

数字 $i$ 表示当前搜索到的位置，我们从数字的最高位开始搜索，即二进制字符串的首字符；
数字 $\textit{pre}$ 表示上一个数字二进制位上的数字，对于本题， $\textit{pre}$ 的初始值为 $0$ ；
布尔值 $\textit{limit}$ 表示可填的数字的限制，如果无限制，那么可以选择 $[0,1]$ ，否则，只能选择 $[0, \textit{up}]$ 。

函数的执行过程如下：

如果 $i$ 超过了数字 $n$ 的长度，即 $i \lt 0$ ，说明搜索结束，直接返回 $1$ 。否则，我们从 $0$ 到 $\textit{up}$ 枚举位置 $i$ 的数字 $j$ ，对于每一个 $j$ ：

如果 $\textit{pre}$ 和 $j$ 都为 $1$ ，说明有连续的 $1$ ，直接跳过；
否则，我们递归到下一层，更新 $\textit{pre}$ 为 $j$ ，并将 $\textit{limit}$ 更新为 $\textit{limit}$ 与 $j$ 是否等于 $\textit{up}$ 的逻辑与。

最后，我们将所有递归到下一层的结果累加，即为答案。

时间复杂度 $O(\log n)$ ，空间复杂度 $O(\log n)$ 。其中 $n$ 为题目给定的正整数。

相似题目：

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def findIntegers(self, n: int) -> int:
        @cache
        def dfs(i: int, pre: int, limit: bool) -> int:
            if i < 0:
                return 1
            up = (n >> i & 1) if limit else 1
            ans = 0
            for j in range(up + 1):
                if pre and j:
                    continue
                ans += dfs(i - 1, j, limit and j == up)
            return ans

        return dfs(n.bit_length() - 1, 0, True)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Tests the candidate's understanding of dynamic programming and state transitions.
question_mark
Evaluates the candidate’s ability to handle large inputs efficiently with bit manipulation.
question_mark
Assesses the ability to recognize patterns in the problem, such as the Fibonacci-like sequence in counting valid numbers.

warning

常见陷阱

外企场景

error
Confusing consecutive ones with other binary patterns, leading to incorrect counting.
error
Inefficient brute force approaches that iterate through all numbers up to n instead of using dynamic programming.
error
Overlooking the importance of bit manipulation and Fibonacci-like properties in optimizing the solution for large values of n.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to count numbers with consecutive ones allowed but limited to a certain number of times.
arrow_right_alt
Adapt the problem to count numbers with even or odd numbers of bits without consecutive ones.
arrow_right_alt
Extend the problem to include additional constraints on the binary representations, such as limiting the total number of 1's.

help

常见问题

外企场景

继续练习

#583 两个字符串的删除操作 #576 出界的路径数 #629 K 个逆序对数组