Hard
题目描述
给定两个整数 n 和 k。
对于任何正整数 x，定义以下序列：
p₀ = xpᵢ₊₁ = popcount(pᵢ)对于所有i >= 0，其中popcount(y)是y的二进制表示中设置位（1）的数量。
这个序列最终会达到值 1。
x 的 popcount-depth 定义为使得 pᵈ = 1 的最小整数 d >= 0。
例如，如果 x = 7（二进制表示为 “111”），那么序列是：7 → 3 → 2 → 1，所以 7 的 popcount-depth 是 3。
你的任务是确定范围 [1, n] 中 popcount-depth 恰好等于 k 的整数数量。
返回这样的整数数量。
示例 1：
输入：n = 4, k = 1
输出：2
解释：
范围 [1, 4] 中 popcount-depth 恰好等于 1 的整数如下：
x | 二进制 | 序列
2 | "10" | 2 → 1
4 | "100" | 4 → 1
因此答案是 2。
示例 2：
输入：n = 7, k = 2
输出：3
解释：
范围 [1, 7] 中 popcount-depth 恰好等于 2 的整数如下：
x | 二进制 | 序列
3 | "11" | 3 → 2 → 1
5 | "101" | 5 → 2 → 1
6 | "110" | 6 → 2 → 1
因此答案是 3。
约束条件：
1 <= n <= 10¹⁵0 <= k <= 5
解题思路
这道题需要用到数位动态规划和组合数学的知识。
核心思路：
预计算深度表：首先计算每个可能的 1 的数量（0 到 64）对应的 popcount-depth。由于最多 64 位，1 的数量最多为 64，而 64 的 popcount 是 2，2 的 popcount 是 1，所以深度最多为 3。
数位动态规划：使用数位 DP 统计不超过 n 的数字中，恰好有 j 个 1 的数字个数。定义状态
dp[pos][ones][tight]：pos：当前处理到第几位ones：已经选择的 1 的数量tight：是否受到上界限制
状态转移：对于每一位，可以选择放 0 或 1（如果 tight 为真，还要考虑不超过 n 对应位的限制）。
合并答案：对于每个可能的 1 的数量 j，如果其对应的 popcount-depth 等于 k，就将其对应的数字个数加入答案。
算法步骤：
- 预计算深度数组
depth[j]，表示 j 个 1 对应的 popcount-depth - 使用数位 DP 计算
count[j]，表示不超过 n 且恰好有 j 个 1 的数字个数 - 遍历所有 j，如果
depth[j] == k，将count[j]加入答案
代码实现
class Solution {
public:
long long popcountDepth(long long n, int k) {
// 预计算每个1的个数对应的popcount-depth
vector<int> depth(65, 0);
for (int i = 1; i <= 64; i++) {
int cur = i;
int d = 0;
while (cur > 1) {
cur = __builtin_popcount(cur);
d++;
}
depth[i] = d;
}
// 数位DP
string binary = "";
long long temp = n;
while (temp > 0) {
binary = (char)('0' + temp % 2) + binary;
temp /= 2;
}
int len = binary.length();
vector<vector<vector<long long>>> dp(len + 1, vector<vector<long long>>(65, vector<long long>(2, -1)));
function<long long(int, int, bool)> solve = [&](int pos, int ones, bool tight) -> long long {
if (pos == len) {
return ones;
}
if (dp[pos][ones][tight] != -1) {
return dp[pos][ones][tight];
}
int limit = tight ? (binary[pos] - '0') : 1;
long long result = 0;
for (int digit = 0; digit <= limit; digit++) {
bool newTight = tight && (digit == limit);
result += solve(pos + 1, ones + digit, newTight);
}
return dp[pos][ones][tight] = result;
};
// 计算每个1的个数对应的数字个数
vector<long long> count(65, 0);
for (int i = 0; i <= 64; i++) {
fill(dp.begin(), dp.end(), vector<vector<long long>>(65, vector<long long>(2, -1)));
count[i] = solve(0, 0, true);
if (i > 0) count[i] -= count[i-1];
}
long long answer = 0;
for (int i = 1; i <= 64; i++) {
if (depth[i] == k) {
answer += count[i];
}
}
return answer;
}
};
class Solution:
def popcountDepth(self, n: int, k: int) -> int:
# 预计算每个1的个数对应的popcount-depth
depth = [0] * 65
for i in range(1, 65):
cur = i
d = 0
while cur > 1:
cur = bin(cur).count('1')
d += 1
depth[i] = d
# 数位DP
binary = bin(n)[2:]
length = len(binary)
from functools import lru_cache
@lru_cache(None)
def dp(pos, ones, tight):
if pos == length:
return 1 if ones >= 0 else 0
limit = int(binary[pos]) if tight else 1
result = 0
for digit in range(limit + 1):
new_tight = tight and (digit == limit)
result += dp(pos + 1, ones - digit, new_tight)
return result
# 计算每个1的个数对应的数字个数
count = [0] * 65
for i in range(65):
count[i] = dp(0, i, True)
# 转换为差分数组
for i in range(64, 0, -1):
count[i] -= count[i-1]
# 计算答案
answer = 0
for i in range(1, 65):
if depth[i] == k:
answer += count[i]
return answer
public class Solution {
public long PopcountDepth(long n, int k) {
// 预计算每个1的个数对应的popcount-depth
int[] depth = new int[65];
for (int i = 1; i <= 64; i++) {
int cur = i;
int d = 0;
while (cur > 1) {
cur = System.Numerics.BitOperations.PopCount((uint)cur);
d++;
}
depth[i] = d;
}
// 数位DP
string binary = Convert.ToString(n, 2);
int len = binary.Length;
long[,,] memo = new long[len + 1, 65, 2];
for (int i = 0; i <= len; i++) {
for (int j = 0; j <= 64; j++) {
for (int k2 = 0; k2 < 2; k2++) {
memo[i, j, k2] = -1;
}
}
}
long Solve(int pos, int ones, bool tight) {
if (pos == len) {
return ones;
}
int tightInt = tight ? 1 : 0;
if (memo[pos, ones, tightInt] != -1) {
return memo[pos, ones, tightInt];
}
int limit = tight ? (binary[pos] - '0') : 1;
long result = 0;
for (int digit = 0; digit <= limit; digit++) {
bool newTight = tight && (digit == limit);
result += Solve(pos + 1, ones + digit, newTight);
}
return memo[pos, ones, tightInt] = result;
}
// 计算每个1的个数对应的数字个数
long[] count = new long[65];
for (int i = 0; i <= 64; i++) {
for (int j = 0; j <= len; j++) {
for (int l = 0; l <= 64; l++) {
for (int m = 0; m < 2; m++) {
memo[j, l, m] = -1;
}
}
}
count[i] = Solve(0, 0, true);
if (i > 0) count[i] -= count[i-1];
}
long answer = 0;
for (int i = 1; i <= 64; i++) {
if (depth[i] == k) {
answer += count[i];
}
}
return answer;
}
}
/**
* @param {number} n
* @param {number} k
* @return {number}
*/
var popcountDepth = function(n, k) {
function popcount(x) {
let count = 0;
while (x > 0) {
count += x & 1;
x >>= 1;
}
return count;
}
function getDepth(x) {
let depth = 0;
while (x !== 1) {
x = popcount(x);
depth++;
}
return depth;
}
if (k === 0) return n >= 1 ? 1 : 0;
// Find the range of popcount values that lead to depth k-1
const targetPopcounts = new Set();
for (let pc = 1; pc <= 64; pc++) {
if (getDepth(pc) === k - 1) {
targetPopcounts.add(pc);
}
}
if (targetPopcounts.size === 0) return 0;
function countWithPopcount(limit, target) {
const s = limit.toString(2);
const memo = new Map();
function dp(pos, count, tight) {
if (pos === s.length) {
return count === target ? 1 : 0;
}
const key = `${pos},${count},${tight}`;
if (memo.has(key)) return memo.get(key);
const maxDigit = tight ? parseInt(s[pos]) : 1;
let result = 0;
for (let digit = 0; digit <= maxDigit; digit++) {
result += dp(
pos + 1,
count + digit,
tight && digit === maxDigit
);
}
memo.set(key, result);
return result;
}
return dp(0, 0, true);
}
let result = 0;
for (const target of targetPopcounts) {
result += countWithPopcount(n, target);
}
return result;
};
复杂度分析
| 复杂度类型 | 复杂度 |
|---|---|
| 时间复杂度 | O(log²n × 64) |
| 空间复杂度 | O(log n × 64) |
其中 log n 是 n 的二进制位数，64 是可能的 1 的数量上限。数位 DP 需要遍历每个位置和每种可能的 1 的数量，预计算深度数组的复杂度是常数。