LeetCode 3621. 位计数深度为 K 的整数数目 I Python3 实现pythonfrom functools import lru_cacheclass Solution:def popcountDepth(self, n: int, k: int) - int:# k0只有 1 的深度为 0if k 0:return 1 if n 1 else 0# 预处理 1~60 的 popcount-depth# n 1e15 2^50popcount 最大不超过 50def get_depth(x: int) - int:if x 1:return 0return 1 get_depth(bin(x).count(1))# 找出所有满足 depth(c) k-1 的 popcount 值 ctargets [i for i in range(1, 61) if get_depth(i) k - 1]if not targets:return 0bits bin(n)[2:] # n 的二进制表示m len(bits)ans 0for c in targets:# 数位 DP统计 [0, n] 中二进制恰好有 c 个 1 的数的个数lru_cache(maxsizeNone)def dfs(i: int, j: int, tight: bool) - int:if j c:return 0 # 1 的个数已超剪枝if i m:return 1 if j c else 0limit int(bits[i]) if tight else 1total 0for d in range(limit 1):total dfs(i 1, j d, tight and d limit)return totalans dfs(0, 0, True)dfs.cache_clear() # 清除缓存为下一个 c 做准备# k1 的特殊处理popcount1 包含 x1但 depth(1)0需排除if k 1:ans - 1return ans---核心思路步骤 说明深度定义 D(1) 0D(x) 1 D(popcount(x))x 1目标转化 D(x) k ⟺ popcount(x) c 且 D(c) k - 1预处理 对 1 ~ 60 预计算深度找出所有合法的 c数位 DP 对每个 c统计 [1, n] 中二进制恰好有 c 个 1 的整数个数边界修正 k 1 时c 1 会把 x 1 算进去但 D(1) 0需减去时间复杂度 O(log² n)数位 DP 状态数 O(log n)二分/枚举 c 的个数很少空间复杂度 O(log² n)lru_cache 记忆化
