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

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

```javascript
/**
* @param {number} n
* @param {number} k
* @return {number}
*/
var popcountDepth = function(n, k) {
// k=0：只有 1 的深度为 0
if (k === 0) {
return n >= 1 ? 1 : 0;
}

// 计算一个整数的 popcount（二进制 1 的个数）
const popcount = (x) => {
let cnt = 0;
while (x > 0) {
cnt += (x & 1);
x >>= 1;
}
return cnt;
};

// 预处理 1~60 的 popcount-depth
const depthMemo = new Array(65).fill(-1);
depthMemo[1] = 0;

const getDepth = (x) => {
if (x === 1) return 0;
if (depthMemo[x] !== -1) return depthMemo[x];
depthMemo[x] = 1 + getDepth(popcount(x));
return depthMemo[x];
};

// 找出所有满足 depth(c) == k-1 的 popcount 值 c
const targets = [];
for (let i = 1; i <= 60; i++) {
if (getDepth(i) === k - 1) {
targets.push(i);
}
}

if (targets.length === 0) return 0;

const s = n.toString(2); // n 的二进制字符串
const m = s.length;
let ans = 0;

for (const c of targets) {
// memo[pos][ones]：仅非 tight 状态有效
const memo = Array.from({ length: m }, () => new Array(c + 1).fill(null));

const dfs = (pos, ones, tight) => {
if (ones > c) return 0; // 1 的个数已超，剪枝
if (pos === m) {
return ones === c ? 1 : 0;
}

if (!tight && memo[pos][ones] !== null) {
return memo[pos][ones];
}

const limit = tight ? parseInt(s[pos]) : 1;
let res = 0;

for (let d = 0; d <= limit; d++) {
res += dfs(pos + 1, ones + d, tight && (d === limit));
}

if (!tight) {
memo[pos][ones] = res;
}
return res;
};

ans += dfs(0, 0, true);
}

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

return ans;
};
```

---

JavaScript 实现要点

要点 说明
`n.toString(2)` 将 `n` 转为二进制字符串，作为数位 DP 的上界
手动记忆化 用二维数组 `memo[pos][ones]` 存储非 `tight` 状态的结果（`null` 表示未计算）
闭包递归 `dfs` 作为闭包捕获 `s`、`m`、`c`、`memo`，避免全局污染
类型安全 `n ≤ 10¹⁵ < 2⁵³`，JavaScript `number` 可精确表示，无需 `BigInt`
k=1 修正 `popcount = 1` 会把 `x = 1` 算入，但其深度为 0，需减去

时间复杂度： `O(log² n)`

空间复杂度： `O(log² n)`