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

我来为你详细解析 LeetCode 600. 不含连续1的非负整数这道经典题。题目理解给定整数n统计[0, n]范围内二进制表示不含连续两个1的非负整数个数。示例n 50: 000 ✓1: 001 ✓2: 010 ✓3: 011 ✗连续两个14: 100 ✓5: 101 ✓答案5核心思路数位DP 斐波那契性质这道题有两个关键洞察斐波那契性质设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]即斐波那契数列逐位统计数位DP思想将n转为二进制从高到低遍历遇到1时可以先将该位填0后面任意填累加dp[i]如果前一位已经是1当前位只能填0否则非法如果顺利遍历完说明n本身合法结果 1完整代码实现publicintfindIntegers(intn){// 1. 预处理斐波那契数组// dp[i] 表示长度为 i 的二进制数中不含连续1的个数int[]dpnewint[31];dp[0]1;// 空串算1种dp[1]2;// 0, 1for(inti2;i31;i){dp[i]dp[i-1]dp[i-2];// 斐波那契}// 2. 逐位处理n的二进制表示intres0;intpreBit0;// 前一位是什么0或1intk30;// 从最高位开始n 10^9 2^30while(k0){// 检查第k位是否为1if((n(1k))!0){// 当前位是1我们可以填0后面k位任意合法resdp[k];// 如果前一位也是1出现连续1n本身不合法直接返回if(preBit1){returnres;// 不包含n本身}// 前一位设为1继续处理下一位preBit1;}else{// 当前位是0前一位设为0preBit0;}k--;}// 如果遍历完没有出现连续1n本身是合法的returnres1;}详细图解以 n 5 为例n 5 101 (二进制3位) k2 (第2位是1): 填0后面2位任意: dp[2] 3 (00, 01, 10) 实际填1preBit1 k1 (第1位是0): 填0preBit0 k0 (第0位是1): 填0后面0位任意: dp[0] 1 实际填1preBit1 遍历完成n101本身合法res 3 1 1 5 ✓复杂度分析维度 复杂度 说明时间 O(log n) 二进制位数最多30位空间 O(1) 固定大小的dp数组关键点总结斐波那契规律dp[i] dp[i-1] dp[i-2]贪心累加遇到1就累加dp[k]将该位变0后的所有可能连续1检测前一位是1且当前位是1时立即返回边界处理最后要判断n本身是否合法类似题目推荐LeetCode 902. 最大为 N 的数字组合数位DPLeetCode 1012. 至少有1位重复的数字LeetCode 2376. 统计特殊整数需要我用另一种方法如纯记忆化搜索再实现一遍或者详细解释某个边界情况吗