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

发布于 2024-08-05  35 次阅读


给定一个正整数 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

class Solution {
public int findIntegers(int n) {
int m = Integer.SIZE - Integer.numberOfLeadingZeros(n);
int[][] memo = new int[m][2];
for (int[] row : memo) {
Arrays.fill(row, -1); // -1 表示没有计算过
}
return dfs(m - 1, 0, true, n, memo); // 从高位到低位
}
// pre 表示前一个比特位填的数
private int dfs(int i, int pre, boolean isLimit, int n, int[][] memo) {
if (i < 0) {
return 1;
}
if (!isLimit && memo[i][pre] >= 0) { // 之前计算过
return memo[i][pre];
}
int up = isLimit ? n >> i & 1 : 1;
int res = dfs(i - 1, 0, isLimit && up == 0, n, memo); // 填 0
if (pre == 0 && up == 1) { // 可以填 1
res += dfs(i - 1, 1, isLimit, n, memo); // 填 1
}
if (!isLimit) {
memo[i][pre] = res; // 记忆化
}
return res;
}
}