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) {// k0只有 1 的深度为 0if (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-depthconst 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 值 cconst 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);}// k1 的特殊处理popcount1 包含 x1但 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 可精确表示无需 BigIntk1 修正 popcount 1 会把 x 1 算入但其深度为 0需减去时间复杂度 O(log² n)空间复杂度 O(log² n)