给定一个正整数 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 <= 109
这道题实际上是求在给定区间
对于区间
不过对于本题而言，我们只需要求出区间
这里我们用记忆化搜索来实现数位 DP。从起点向下搜索，到最底层得到方案数，一层层向上返回答案并累加，最后从搜索起点得到最终的答案。
基本步骤如下：
- 将数字
$n$ 转为二进制数组$a$ ，其中$a[1]$ 为最低位，而$a[len]$ 为最高位； - 根据题目信息，设计函数
$dfs()$ ，对于本题，我们定义$dfs(pos, pre, limit)$ ，答案为$dfs(len, 1, true)$ 。
其中：
-
pos表示数字的位数，从末位或者第一位开始，一般根据题目的数字构造性质来选择顺序。对于本题，我们选择从高位开始，因此，pos的初始值为len； -
pre表示当前数字二进制位上的数字，对于本题，pre的初始值为0； -
limit表示可填的数字的限制，如果无限制，那么可以选择$[0,1]$ ，否则，只能选择$[0,..a[pos]]$ 。如果limit为true且已经取到了能取到的最大值，那么下一个limit同样为true；如果limit为true但是还没有取到最大值，或者limit为false，那么下一个limit为false。
关于函数的实现细节，可以参考下面的代码。
时间复杂度
相似题目：
class Solution:
def findIntegers(self, n: int) -> int:
@cache
def dfs(pos, pre, limit):
if pos <= 0:
return 1
up = a[pos] if limit else 1
ans = 0
for i in range(up + 1):
if pre == 1 and i == 1:
continue
ans += dfs(pos - 1, i, limit and i == up)
return ans
a = [0] * 33
l = 0
while n:
l += 1
a[l] = n & 1
n >>= 1
return dfs(l, 0, True)class Solution {
private int[] a = new int[33];
private int[][] dp = new int[33][2];
public int findIntegers(int n) {
int len = 0;
while (n > 0) {
a[++len] = n & 1;
n >>= 1;
}
for (var e : dp) {
Arrays.fill(e, -1);
}
return dfs(len, 0, true);
}
private int dfs(int pos, int pre, boolean limit) {
if (pos <= 0) {
return 1;
}
if (!limit && dp[pos][pre] != -1) {
return dp[pos][pre];
}
int up = limit ? a[pos] : 1;
int ans = 0;
for (int i = 0; i <= up; ++i) {
if (!(pre == 1 && i == 1)) {
ans += dfs(pos - 1, i, limit && i == up);
}
}
if (!limit) {
dp[pos][pre] = ans;
}
return ans;
}
}class Solution {
public:
int a[33];
int dp[33][2];
int findIntegers(int n) {
int len = 0;
while (n) {
a[++len] = n & 1;
n >>= 1;
}
memset(dp, -1, sizeof dp);
return dfs(len, 0, true);
}
int dfs(int pos, int pre, bool limit) {
if (pos <= 0) {
return 1;
}
if (!limit && dp[pos][pre] != -1) {
return dp[pos][pre];
}
int ans = 0;
int up = limit ? a[pos] : 1;
for (int i = 0; i <= up; ++i) {
if (!(pre == 1 && i == 1)) {
ans += dfs(pos - 1, i, limit && i == up);
}
}
if (!limit) {
dp[pos][pre] = ans;
}
return ans;
}
};func findIntegers(n int) int {
a := make([]int, 33)
dp := make([][2]int, 33)
for i := range dp {
dp[i] = [2]int{-1, -1}
}
l := 0
for n > 0 {
l++
a[l] = n & 1
n >>= 1
}
var dfs func(int, int, bool) int
dfs = func(pos, pre int, limit bool) int {
if pos <= 0 {
return 1
}
if !limit && dp[pos][pre] != -1 {
return dp[pos][pre]
}
up := 1
if limit {
up = a[pos]
}
ans := 0
for i := 0; i <= up; i++ {
if !(pre == 1 && i == 1) {
ans += dfs(pos-1, i, limit && i == up)
}
}
if !limit {
dp[pos][pre] = ans
}
return ans
}
return dfs(l, 0, true)
}