目标
给定一个正整数 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说明:
- 1 <= n <= 10^9
思路
给定一个正整数n，求 [0, n] 范围内整数的二进制表示中不含连续1的整数个数。
由于n最大10^9，如果挨个判断整数是否含连续的bit 1，实际复杂度为O(31n)，超时。
既然暴力解不行只能考虑其它方法。分析n的二进制表示，将问题转换为一定限制条件下的排列组合问题。求得二进制表示之后可以使用dfs来计算组合数。如果不使用记忆化搜索同样会超时，这里使用状态压缩来记录重复的子问题。状态指方法参数的组合，如果cur为1，则将高位置1与index相与，第二个维度0表示不可以将0改为1，1表示可以将0改为1。
官网题解使用的是递推。
代码
/**
* @date 2024-08-05 10:20
*/
public class FindIntegers600 {
public int findIntegers(int n) {
List<Integer> bitmap = new ArrayList<>(32);
while (n > 0) {
bitmap.add(n & 1);
n >>= 1;
}
int[][] mem = new int[(1 << 5) | (bitmap.size() - 1)][2];
return dfs(0, bitmap, bitmap.size() - 1, false, mem);
}
public int dfs(int pre, List<Integer> bitmap, int index, boolean zeroToOne, int[][] mem) {
int cur = bitmap.get(index);
if (index == 0) {
return pre == 0 && (cur == 1 || zeroToOne) ? 2 : 1;
}
int res = 0;
index--;
int size = bitmap.size();
int key = (1 << 5) | index;
int zto = zeroToOne ? 1 : 0;
if (pre == 1 && cur == 1) {
// 如果前一个是1，当前也是1，将1改为0，允许后续的0改为1
if (mem[index][1] == 0) {
mem[index][1] = dfs(cur - 1, bitmap, index, true, mem);
}
res = mem[index][1];
} else if (pre == 0 && cur == 1) {
// 如果前一个是0，当前是1，将1改为0，允许后续的0改为1，或者当前不变，后续是否允许0变1取决于zeroToOne
if (mem[index][1] == 0) {
mem[index][1] = dfs(cur - 1, bitmap, index, true, mem);
}
if (mem[key][zto] == 0) {
mem[key][zto] = dfs(cur, bitmap, index, zeroToOne, mem);
}
res = mem[index][1] + mem[key][zto];
} else if (pre == 0 && cur == 0) {
// 如果前一个是0，当前是0，当前不变，后续是否允0变1许取决于zeroToOne，如果当前zeroToOne为true，将0改为1
if (mem[index][zto] == 0) {
mem[index][zto] = dfs(cur, bitmap, index, zeroToOne, mem);
}
res = mem[index][zto];
if (zeroToOne) {
if (mem[key][zto] == 0) {
mem[key][zto] = dfs(cur + 1, bitmap, index, zeroToOne, mem);
}
res += mem[key][zto];
}
} else {
// 如果前一个是1，当前是0，当前不变，后续是否允许0变1取决于zeroToOne
if (mem[index][zto] == 0) {
mem[index][zto] = dfs(cur, bitmap, index, zeroToOne, mem);
}
res = mem[index][zto];
}
return res;
}
}
性能
