class Solution {
public:
int countKReducibleNumbers(string s, int k) {
}
};
3352. 统计小于 N 的 K 可约简整数
给你一个 二进制 字符串 s，它表示数字 n 的二进制形式。
同时，另给你一个整数 k。
如果整数 x 可以通过最多 k 次下述操作约简到 1 ，则将整数 x 称为 k-可约简 整数：
x 替换为其二进制表示中的置位数（即值为 1 的位）。例如，数字 6 的二进制表示是 "110"。一次操作后，它变为 2（因为 "110" 中有两个置位）。再对 2（二进制为 "10"）进行操作后，它变为 1（因为 "10" 中有一个置位）。
返回小于 n 的正整数中有多少个是 k-可约简 整数。
由于答案可能很大，返回结果需要对 109 + 7 取余。
二进制中的置位是指二进制表示中值为 1 的位。
示例 1：
输入： s = "111", k = 1
输出： 3
解释：
n = 7。小于 7 的 1-可约简整数有 1，2 和 4。
示例 2：
输入： s = "1000", k = 2
输出： 6
解释：
n = 8。小于 8 的 2-可约简整数有 1，2，3，4，5 和 6。
示例 3：
输入： s = "1", k = 3
输出： 0
解释：
小于 n = 1 的正整数不存在，因此答案为 0。
提示：
1 <= s.length <= 800s 中没有前导零。s 仅由字符 '0' 和 '1' 组成。1 <= k <= 5原站题解
cpp 解法, 执行用时: 194 ms, 内存消耗: 49.6 MB, 提交时间: 2024-11-17 23:37:56
class Solution {
public:
int countKReducibleNumbers(string s, int k) {
const int MOD = 1'000'000'007;
int n = s.length();
vector<vector<int>> memo(n, vector<int>(n, -1));
auto dfs = [&](auto& dfs, int i, int left1, bool is_limit) -> int {
if (i == n) {
return !is_limit && left1 == 0;
}
if (!is_limit && memo[i][left1] != -1) {
return memo[i][left1];
}
int up = is_limit ? s[i] - '0' : 1;
int res = 0;
for (int d = 0; d <= min(up, left1); d++) {
res = (res + dfs(dfs, i + 1, left1 - d, is_limit && d == up)) % MOD;
}
if (!is_limit) {
memo[i][left1] = res;
}
return res;
};
long long ans = 0;
vector<int> f(n);
for (int i = 1; i < n; i++) {
f[i] = f[__builtin_popcount(i)] + 1;
if (f[i] <= k) {
// 计算有多少个二进制数恰好有 i 个 1
ans += dfs(dfs, 0, i, true);
}
}
return ans % MOD;
}
};
java 解法, 执行用时: 141 ms, 内存消耗: 51.4 MB, 提交时间: 2024-11-17 23:37:32
class Solution {
private static final int MOD = 1_000_000_007;
public int countKReducibleNumbers(String S, int k) {
char[] s = S.toCharArray();
int n = s.length;
int[][] memo = new int[n][n];
for (int[] row : memo) {
Arrays.fill(row, -1);
}
long ans = 0;
int[] f = new int[n];
for (int i = 1; i < n; i++) {
f[i] = f[Integer.bitCount(i)] + 1;
if (f[i] <= k) {
// 计算有多少个二进制数恰好有 i 个 1
ans += dfs(0, i, true, s, memo);
}
}
return (int) (ans % MOD);
}
private int dfs(int i, int left1, boolean isLimit, char[] s, int[][] memo) {
if (i == s.length) {
return !isLimit && left1 == 0 ? 1 : 0;
}
if (!isLimit && memo[i][left1] != -1) {
return memo[i][left1];
}
int up = isLimit ? s[i] - '0' : 1;
int res = 0;
for (int d = 0; d <= Math.min(up, left1); d++) {
res = (res + dfs(i + 1, left1 - d, isLimit && d == up, s, memo)) % MOD;
}
if (!isLimit) {
memo[i][left1] = res;
}
return res;
}
}
golang 解法, 执行用时: 140 ms, 内存消耗: 14.1 MB, 提交时间: 2024-11-17 23:37:16
func countKReducibleNumbers(s string, k int) (ans int) {
const mod = 1_000_000_007
n := len(s)
memo := make([][]int, n)
for i := range memo {
memo[i] = make([]int, n)
for j := range memo[i] {
memo[i][j] = -1
}
}
var dfs func(int, int, bool) int
dfs = func(i, left1 int, isLimit bool) (res int) {
if i == n {
if !isLimit && left1 == 0 {
return 1
}
return
}
if !isLimit {
p := &memo[i][left1]
if *p >= 0 {
return *p
}
defer func() { *p = res }()
}
up := 1
if isLimit {
up = int(s[i] - '0')
}
for d := 0; d <= min(up, left1); d++ {
res += dfs(i+1, left1-d, isLimit && d == up)
}
return res % mod
}
f := make([]int, n)
for i := 1; i < n; i++ {
f[i] = f[bits.OnesCount(uint(i))] + 1
if f[i] <= k {
// 计算有多少个二进制数恰好有 i 个 1
ans += dfs(0, i, true)
}
}
return ans % mod
}
python3 解法, 执行用时: 6194 ms, 内存消耗: 224.3 MB, 提交时间: 2024-11-17 23:36:59
class Solution:
def countKReducibleNumbers(self, s: str, k: int) -> int:
MOD = 1_000_000_007
n = len(s)
@cache
def dfs(i: int, left1: int, is_limit: bool) -> int:
if i == n:
return 0 if is_limit or left1 else 1
up = int(s[i]) if is_limit else 1
res = 0
for d in range(min(up, left1) + 1):
res += dfs(i + 1, left1 - d, is_limit and d == up)
return res % MOD
ans = 0
f = [0] * n
for i in range(1, n):
f[i] = f[i.bit_count()] + 1
if f[i] <= k:
# 计算有多少个二进制数恰好有 i 个 1
ans += dfs(0, i, True)
dfs.cache_clear() # 防止爆内存
return ans % MOD