class Solution {
public:
int numberOfBeautifulIntegers(int low, int high, int k) {
}
};
8013. 范围中美丽整数的数目
给你正整数 low ，high 和 k 。
如果一个数满足以下两个条件，那么它是 美丽的 ：
k 整除。请你返回范围 [low, high] 中美丽整数的数目。
示例 1：
输入：low = 10, high = 20, k = 3 输出：2 解释：给定范围中有 2 个美丽数字：[12,18] - 12 是美丽整数，因为它有 1 个奇数数位和 1 个偶数数位，而且可以被 k = 3 整除。 - 18 是美丽整数，因为它有 1 个奇数数位和 1 个偶数数位，而且可以被 k = 3 整除。 以下是一些不是美丽整数的例子： - 16 不是美丽整数，因为它不能被 k = 3 整除。 - 15 不是美丽整数，因为它的奇数数位和偶数数位的数目不相等。 给定范围内总共有 2 个美丽整数。
示例 2：
输入：low = 1, high = 10, k = 1 输出：1 解释：给定范围中有 1 个美丽数字：[10] - 10 是美丽整数，因为它有 1 个奇数数位和 1 个偶数数位，而且可以被 k = 1 整除。 给定范围内总共有 1 个美丽整数。
示例 3：
输入：low = 5, high = 5, k = 2 输出：0 解释：给定范围中有 0 个美丽数字。 - 5 不是美丽整数，因为它的奇数数位和偶数数位的数目不相等。
提示：
0 < low <= high <= 1090 < k <= 20原站题解
cpp 解法, 执行用时: 16 ms, 内存消耗: 6 MB, 提交时间: 2023-08-21 10:25:28
class Solution {
int calc(int high, int k) {
auto s = to_string(high);
int n = s.length(), memo[n][k + 1][n * 2 + 1];
memset(memo, -1, sizeof(memo)); // -1 表示没有计算过
function<int(int, int, int, bool, bool)> dfs;
dfs = [&](int i, int val, int diff, bool is_limit, bool is_num) -> int {
if (i == n)
return is_num && val == 0 && diff == n; // 找到了一个合法数字
if (!is_limit && is_num && memo[i][val][diff] != -1)
return memo[i][val][diff];
int res = 0;
if (!is_num) // 可以跳过当前数位
res = dfs(i + 1, val, diff, false, false);
int up = is_limit ? s[i] - '0' : 9; // 如果前面填的数字都和 high 的一样，那么这一位至多填数字 s[i]（否则就超过 high 啦）
for (int d = 1 - is_num; d <= up; d++) // 枚举要填入的数字 d
res += dfs(i + 1, (val * 10 + d) % k, diff + d % 2 * 2 - 1, is_limit && d == up, true);
if (!is_limit && is_num)
memo[i][val][diff] = res; // 记忆化
return res;
};
return dfs(0, 0, n, true, false);
}
public:
int numberOfBeautifulIntegers(int low, int high, int k) {
return calc(high, k) - calc(low - 1, k);
}
};
golang 解法, 执行用时: 8 ms, 内存消耗: 5 MB, 提交时间: 2023-08-21 10:24:38
func numberOfBeautifulIntegers(low, high, k int) int {
calc := func(high int) int {
s := strconv.Itoa(high)
n := len(s)
memo := make([][][]int, n)
for i := range memo {
memo[i] = make([][]int, k+1)
for j := range memo[i] {
memo[i][j] = make([]int, n*2+1)
for k := range memo[i][j] {
memo[i][j][k] = -1 // -1 表示没有计算过
}
}
}
var dfs func(int, int, int, bool, bool) int
dfs = func(i, val, diff int, isLimit, isNum bool) (res int) {
if i == n {
if isNum && val == 0 && diff == n {
return 1 // 找到了一个合法数字
}
return 0
}
if !isLimit && isNum {
p := &memo[i][val][diff]
if *p >= 0 {
return *p
}
defer func() { *p = res }() // 记忆化搜索
}
if !isNum { // 可以跳过当前数位
res += dfs(i+1, val, diff, false, false)
}
up := 9
if isLimit {
up = int(s[i] - '0') // 如果前面填的数字都和 high 的一样，那么这一位至多填数字 s[i]（否则就超过 high 啦）
}
d := 0
if !isNum {
d = 1 // 如果前面没有填数字，必须从 1 开始（因为不能有前导零）
}
for ; d <= up; d++ { // 枚举要填入的数字 d
res += dfs(i+1, (val*10+d)%k, diff+d%2*2-1, isLimit && d == up, true)
}
return
}
return dfs(0, 0, n, true, false)
}
return calc(high) - calc(low-1)
}
java 解法, 执行用时: 6 ms, 内存消耗: 40.1 MB, 提交时间: 2023-08-21 10:24:05
class Solution {
public int numberOfBeautifulIntegers(int low, int high, int k) {
return calc(high, k) - calc(low - 1, k);
}
private int calc(int high, int k) {
var s = Integer.toString(high).toCharArray();
int n = s.length;
var memo = new int[n][k][n * 2 + 1];
for (int i = 0; i < n; i++)
for (int j = 0; j < k; j++)
Arrays.fill(memo[i][j], -1); // -1 表示没有计算过
return dfs(0, 0, n, true, false, k, s, memo);
}
private int dfs(int i, int val, int diff, boolean isLimit, boolean isNum, int k, char[] s, int[][][] memo) {
if (i == s.length)
return isNum && val == 0 && diff == s.length ? 1 : 0; // 找到了一个合法数字
if (!isLimit && isNum && memo[i][val][diff] != -1)
return memo[i][val][diff];
int res = 0;
if (!isNum) // 可以跳过当前数位
res = dfs(i + 1, val, diff, false, false, k, s, memo);
int up = isLimit ? s[i] - '0' : 9; // 如果前面填的数字都和 high 的一样，那么这一位至多填数字 s[i]（否则就超过 high 啦）
for (int d = isNum ? 0 : 1; d <= up; d++) // 枚举要填入的数字 d
res += dfs(i + 1, (val * 10 + d) % k, diff + d % 2 * 2 - 1, isLimit && d == up, true, k, s, memo);
if (!isLimit && isNum)
memo[i][val][diff] = res; // 记忆化搜索
return res;
}
}
python3 解法, 执行用时: 232 ms, 内存消耗: 17.5 MB, 提交时间: 2023-08-21 10:23:41
'''
数位dp
'''
class Solution:
def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:
def calc(high: int) -> int:
s = str(high)
@cache # 记忆化搜索
def dfs(i: int, val: int, diff: int, is_limit: bool, is_num: bool) -> int:
if i == len(s):
return int(is_num and val == 0 and diff == 0) # 找到了一个合法数字
res = 0
if not is_num: # 可以跳过当前数位
res = dfs(i + 1, val, diff, False, False)
d0 = 0 if is_num else 1 # 如果前面没有填数字，必须从 1 开始（因为不能有前导零）
up = int(s[i]) if is_limit else 9 # 如果前面填的数字都和 high 的一样，那么这一位至多填 s[i]（否则就超过 high 啦）
for d in range(d0, up + 1): # 枚举要填入的数字 d
res += dfs(i + 1, (val * 10 + d) % k, diff + d % 2 * 2 - 1, is_limit and d == up, True)
return res
return dfs(0, 0, 0, True, False)
return calc(high) - calc(low - 1)