Kimi LeetCode 3621. 位计数深度为 K 的整数数目 I Python3实现

LeetCode 3621. 位计数深度为 K 的整数数目 I Python3 实现

```python
from functools import lru_cache

class Solution:
def popcountDepth(self, n: int, k: int) -> int:
# k=0：只有 1 的深度为 0
if k == 0:
return 1 if n >= 1 else 0

# 预处理 1~60 的 popcount-depth
# n <= 1e15 < 2^50，popcount 最大不超过 50
def get_depth(x: int) -> int:
if x == 1:
return 0
return 1 + get_depth(bin(x).count('1'))

# 找出所有满足 depth(c) == k-1 的 popcount 值 c
targets = [i for i in range(1, 61) if get_depth(i) == k - 1]

if not targets:
return 0

bits = bin(n)[2:] # n 的二进制表示
m = len(bits)
ans = 0

for c in targets:
# 数位 DP：统计 [0, n] 中二进制恰好有 c 个 1 的数的个数
@lru_cache(maxsize=None)
def dfs(i: int, j: int, tight: bool) -> int:
if j > c:
return 0 # 1 的个数已超，剪枝
if i == m:
return 1 if j == c else 0

limit = int(bits[i]) if tight else 1
total = 0
for d in range(limit + 1):
total += dfs(i + 1, j + d, tight and d == limit)
return total

ans += dfs(0, 0, True)
dfs.cache_clear() # 清除缓存，为下一个 c 做准备

# k=1 的特殊处理：popcount=1 包含 x=1，但 depth(1)=0，需排除
if k == 1:
ans -= 1

return ans
```

---

核心思路

步骤 说明
深度定义 `D(1) = 0`，`D(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` 记忆化）