0600. Non-negative Integers without Consecutive Ones¶
题目信息¶
- 题号:
0600
- 难度:
Hard
- 主题:
非负整数、二进制表示、连续一、区间计数
- 原题:
- 重点:
统计区间 [0,n] 且包含两个端点、标准二进制表示中不能出现 11、返回整数个数
题目重述¶
给定正整数 n,统计闭区间 [0, n] 中有多少个非负整数的二进制表示不包含连续的两个 1,并返回数量。
判断使用整数的标准二进制表示,不考虑人为添加的前导零。数字 0 也属于统计范围,其二进制表示不含连续 1,因此始终是一个合法整数。
自建示例¶
区间中同时存在合法和非法整数:
输入:n = 5
输出:5
解释:0、1、2(二进制 10)、4(二进制 100)和 5(二进制 101)合法;3 的二进制 11 含有连续两个 1。
最小正上界:
输入:n = 1
输出:2
解释:区间中只有 0 和 1,二者都不含连续的 1。
斐波那契计数配合高位数位决策¶
从高位到低位处理 n 的二进制表示。f[i] 表示恰好使用不超过 i 个低位时、且最高位可以自由选择的合法二进制串数量,满足 f[i] = f[i-1] + f[i-2]。当 n 的某一位为 1 时,先把该位改成 0,其余低位可以构成 f[i] 个合法数;如果前一位已经是 1,继续沿着 n 扫描会首次出现连续 1,此时直接返回。完整扫描没有冲突时,再把 n 本身计入答案。
C++ 实现¶
class Solution {
public:
int findIntegers(int n) {
int count[31];
count[0] = 1;
count[1] = 2;
for (int i = 2; i <= 30; ++i) {
count[i] = count[i - 1] + count[i - 2];
}
int answer = 0;
int previousBit = 0;
unsigned int value = static_cast<unsigned int>(n);
for (int bit = 30; bit >= 0; --bit) {
if ((value & (1u << bit)) == 0) {
previousBit = 0;
continue;
}
answer += count[bit];
if (previousBit == 1) return answer;
previousBit = 1;
}
return answer + 1;
}
};
代码分析¶
遇到 1 时统计“当前位置取 0”所跳过的整段合法后缀;连续 1 表明 n 的后缀已越过合法边界,不能继续计数。若没有连续 1,最后的 +1 正好加入 n 本身。预计算和高位扫描都只涉及固定的 31 位,时间复杂度和额外空间复杂度均为 O(1)。