代码拉取完成,页面将自动刷新
同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
给定一个正整数 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
这道题实际上是求在给定区间 $[l,..r]$ 中,数字的二进制表示不包含连续的 $1$ 的个数。个数与数的位数以及每个二进制位上的数字有关。我们可以用数位 DP 的思路来解决这道题。数位 DP 中,数的大小对复杂度的影响很小。
对于区间 $[l,..r]$ 问题,我们一般会将其转化为 $[1,..r]$ 然后再减去 $[1,..l - 1]$ 的问题,即:
$$ ans = \sum_{i=1}^{r} ans_i - \sum_{i=1}^{l-1} ans_i $$
不过对于本题而言,我们只需要求出区间 $[0,..r]$ 的值即可。
这里我们用记忆化搜索来实现数位 DP。从起点向下搜索,到最底层得到方案数,一层层向上返回答案并累加,最后从搜索起点得到最终的答案。
基本步骤如下:
其中:
pos
表示数字的位数,从末位或者第一位开始,一般根据题目的数字构造性质来选择顺序。对于本题,我们选择从高位开始,因此,pos
的初始值为 len
;pre
表示当前数字二进制位上的数字,对于本题,pre
的初始值为 0
;limit
表示可填的数字的限制,如果无限制,那么可以选择 $[0,1]$,否则,只能选择 $[0,..a[pos]]$。如果 limit
为 true
且已经取到了能取到的最大值,那么下一个 limit
同样为 true
;如果 limit
为 true
但是还没有取到最大值,或者 limit
为 false
,那么下一个 limit
为 false
。关于函数的实现细节,可以参考下面的代码。
时间复杂度 $O(\log n)$。
相似题目:
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)
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。