题目描述：
给定一个正整数 n ，请你统计在 [0, n] 范围的非负整数中，有多少个整数的二进制表示中不存在 连续的 1 。
数据范围：
$1\le n \le 10^9$
题解：
数位dp，注意等于 $len$ 时需要返回 $!isLead$，也就是不全部是 $0$。但是这个题目用不到 $isLead$，因为前导零不影响连续的 $1$，因此可以不考虑，那么就直接返回 $1$。
另外就是需要将数转换为二进制，而且需要翻转一下。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
string s;
int len;
int dp[30][2];
int dfs(int step, int pre, bool isLimit)
{
if (step == len)
return 1;
if (!isLimit && dp[step][pre] != -1)
return dp[step][pre];
int ans = 0;
int up = isLimit ? s[step] - '0' : 1;
for (int i = 0; i <= up; ++i)
{
if (i == 1 && pre == 1)
continue;
ans += dfs(step + 1, i, isLimit && i == up);
}
if (!isLimit)
dp[step][pre] = ans;
return ans;
}
int findIntegers(int n)
{
while (n)
{
if (n & 1)
s.push_back('1');
else
s.push_back('0');
n >>= 1;
}
reverse(s.begin(), s.end());
len = s.length();
memset(dp, -1, sizeof(dp));
return dfs(0, -1, true);
}
};
|