标签: 动态规划
难度: Hard
给定一个正整数 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 <= 109运行时间: 26 ms
内存: 16.5 MB
class Solution:
def findIntegers(self, n: int) -> int:
s = str(bin(n))[2:]
@cache
def dfs(i, isOne, isLimit):
if i == len(s):
return 1
res = 0
up = s[i] if isLimit else '1'
res += dfs(i+1, False, isLimit and up == '0')
if not isOne and up == '1':
res += dfs(i+1, True, isLimit)
return res
return dfs(0, False, True)
题解使用了深度优先搜索（DFS）和动态规划的方法，结合位操作和记忆化来解决问题。核心思路是递归地构建符合条件的整数，同时确保不会超过给定的上限 n。递归函数 dfs(i, isOne, isLimit) 考虑当前正在处理的比特位索引 i，isOne 表示前一个比特位是否是1，isLimit 表示当前位是否受到 n 的限制。如果当前位 i 等于二进制表示的长度，说明已构建完成一个有效的整数，返回1。函数中，up 变量根据 isLimit 决定当前位能取的最大值。当上一位不是1且当前位可取1时，会继续递归探索。使用 @cache 装饰器对递归结果进行缓存，以避免重复计算。
时间复杂度: O(log n)
空间复杂度: O(log n)
class Solution:
def findIntegers(self, n: int) -> int:
s = str(bin(n))[2:] # 将 n 转换为二进制字符串，去掉前缀'0b'
@cache
def dfs(i, isOne, isLimit):
if i == len(s): # 如果已处理完所有位，返回1
return 1
res = 0
up = s[i] if isLimit else '1' # 根据是否受限决定当前位能取的最大值
res += dfs(i+1, False, isLimit and up == '0') # 探索放置0的情况
if not isOne and up == '1': # 如果前一位不是1且当前位可以放1，则探索放置1的情况
res += dfs(i+1, True, isLimit)
return res
return dfs(0, False, True) # 从第0位开始，没有前一位，且受限于 n
在递归函数dfs中，参数isOne用于记录前一个比特位是否是1，这是为了确保不生成含连续1的整数。如果前一个比特位是1，则当前位不能再放1，只能放0。参数isLimit表示当前正在处理的比特位是否受到输入n的限制。如果isLimit为true，意味着当前比特位要确保不超过n的相应位，否则可以随意设为0或1（不超过上限1）。这两个参数共同影响递归过程，确保生成的整数不仅符合不含连续1的条件，而且不会超过n。
这是因为题目的要求是产生不含连续1的非负整数。如果上一个比特位已经是1，再将当前比特位设为1就会产生连续的1，违反题目要求。因此，只有当上一个比特位是0时，我们才能将当前比特位考虑设置为1，以避免生成连续的1。
变量up用于确定在给定的比特位上可能放置的最大值。当isLimit为true时，表示当前正在生成的数必须小于或等于n，因此当前位的最大值直接受到n的当前位（s[i]）的限制。当isLimit为false时，表示当前位不受n的限制，可以自由放置0或1，因此最大值设为'1'。这种设计确保在不超过n的约束下尽可能自由地生成符合条件的数。
在递归函数dfs中，每次递归调用都对应了将当前比特位设为0或1的两种可能情况（如果条件允许）。每次递归返回的是从当前比特位到最后一位所能生成的所有符合条件的整数数量。通过递归的方式，我们将每个比特位的可能结果累加，最终在递归的顶层得到所有可能的符合条件的整数总数。由于利用了缓存（@cache），确保了相同状态的递归结果不会被重复计算，从而有效避免了重复计数。