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

题目理解

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

示例：n = 5

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

答案：5

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

这道题有两个关键洞察：

1. 斐波那契性质
   设 dp[i] 为长度为 i 的二进制数中不含连续1的个数：

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

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

2. 逐位统计（数位DP思想）
   将 n 转为二进制，从高到低遍历：

• 遇到 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数组

关键点总结

1. 斐波那契规律：dp[i] = dp[i-1] + dp[i-2]
2. 贪心累加：遇到 1 就累加 dp[k]（将该位变0后的所有可能）
3. 连续1检测：前一位是1且当前位是1时，立即返回
4. 边界处理：最后要判断 n 本身是否合法

类似题目推荐

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

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