Kimi LeetCode 600.不含连续1的非负整数 public int findIntegers(int n)

我来为你详细解析 LeetCode 600. 不含连续1的非负整数这道经典题。

题目理解

给定整数 n，统计 [0, n] 范围内二进制表示不含连续两个1的非负整数个数。

示例：n = 5

• 0: 000 ✓
• 1: 001 ✓
• 2: 010 ✓
• 3: 011 ✗（连续两个1）
• 4: 100 ✓
• 5: 101 ✓

答案：5

核心思路：数位DP + 斐波那契性质

这道题有两个关键洞察：

• 最高位为0：后面 i-1 位任意合法，共 dp[i-1] 个
• 最高位为1：次高位必须为0，后面 i-1 位任意合法，共 dp[i-2] 个

所以 dp[i] = dp[i-1] + dp[i-2]，即斐波那契数列！

• 遇到 1 时，可以先将该位填 0，后面任意填（累加 dp[i]）
• 如果前一位已经是 1，当前位只能填 0，否则非法
• 如果顺利遍历完，说明 n 本身合法，结果 +1

完整代码实现

public int findIntegers(int n) {
// 1. 预处理斐波那契数组
// dp[i] 表示长度为 i 的二进制数中不含连续1的个数
int[] dp = new int[31];
dp[0] = 1; // 空串算1种
dp[1] = 2; // 0, 1

for (int i = 2; i < 31; i++) {
dp[i] = dp[i–1] + dp[i–2]; // 斐波那契
}

// 2. 逐位处理n的二进制表示
int res = 0;
int preBit = 0; // 前一位是什么（0或1）
int k = 30; // 从最高位开始（n <= 10^9 < 2^30）

while (k >= 0) {
// 检查第k位是否为1
if ((n & (1 << k)) != 0) {
// 当前位是1，我们可以填0，后面k位任意合法
res += dp[k];

// 如果前一位也是1，出现连续1，n本身不合法，直接返回
if (preBit == 1) {
return res; // 不包含n本身
}

// 前一位设为1，继续处理下一位
preBit = 1;
} else {
// 当前位是0，前一位设为0
preBit = 0;
}
k—;
}

// 如果遍历完没有出现连续1，n本身是合法的
return res + 1;
}

详细图解（以 n = 5 为例）

n = 5 = 101 (二进制，3位)

k=2 (第2位是1):
填0，后面2位任意: dp[2] = 3 (00, 01, 10)
实际填1，preBit=1

k=1 (第1位是0):
填0，preBit=0

k=0 (第0位是1):
填0，后面0位任意: dp[0] = 1
实际填1，preBit=1

遍历完成，n=101本身合法，res = 3 + 1 + 1 = 5 ✓

复杂度分析

维度复杂度说明
时间O(log n)二进制位数，最多30位
空间O(1)固定大小的dp数组

关键点总结

类似题目推荐

• LeetCode 902. 最大为 N 的数字组合（数位DP）
• LeetCode 1012. 至少有1位重复的数字
• LeetCode 2376. 统计特殊整数

需要我用另一种方法（如纯记忆化搜索）再实现一遍，或者详细解释某个边界情况吗？