登录
进制转换（双百）
2025年4月10日 12:09
方法一：数位 DP
这道题实际上是求在给定区间 $[l,..r]$ 中，满足条件的数的个数。个数与数的位数以及每一位上的数字有关。我们可以用数位 DP 的思路来解决这道题。数位 DP 中，数的大小对复杂度的影响很小。
对于区间 $[l,..r]$ 问题，我们一般会将其转化为 $[1,..r]$ 然后再减去 $[1,..l - 1]$ 的问题，即：
$$
ans = \sum_{i=1}^{r} ans_i - \sum_{i=1}^{l-1} ans_i
$$
对于本题而言，我们求出 $[1, \textit{finish}]$ 中满足条件的数的个数，然后减去 $[1, \textit{start} - 1]$ 中满足条件的数的个数，即可得到答案。
这里我们用记忆化搜索来实现数位 DP。从起点向下搜索，到最底层得到方案数，一层层向上返回答案并累加，最后从搜索起点得到最终的答案。
基本步骤如下：
- 先将 $\textit{start}$ 和 $\textit{finish}$ 转化为字符串，方便后续的数位 DP。
- 设计一个函数 $\textit{dfs}(\textit{pos}, \textit{lim})$，表示从第 $\textit{pos}$ 位开始搜索，当前的限制条件为 $\textit{lim}$。
- 如果最大的数字位数小于 $\textit{s}$ 的长度，返回 0。
- 如果当前剩余的数字位数等于 $\textit{s}$ 的长度，判断当前的数字是否满足条件，返回 1 或 0。
- 否则，我们计算当前位的上限 $\textit{up} = \min(\textit{lim} ? \textit{t}[\textit{pos}] : 9, \textit{limit})$。然后遍历当前位的数字 $i$，从 0 到 $\textit{up}$，递归调用 $\textit{dfs}(\textit{pos} + 1, \textit{lim} && i == \textit{t}[\textit{pos}])$，将结果累加到答案中。
- 如果当前的 $\textit{lim}$ 为 false，则将当前的答案存入缓存中，避免重复计算。
- 最后返回答案。
答案为区间 $[1, \textit{finish}]$ 中满足条件的数的个数减去区间 $[1, \textit{start} - 1]$ 中满足条件的数的个数。
###python
class Solution:
def numberOfPowerfulInt(self, start: int, finish: int, limit: int, s: str) -> int:
@cache
def dfs(pos: int, lim: int) -> int:
if len(t) < n:
return 0
if len(t) - pos == n:
return int(s <= t[pos:]) if lim else 1
up = min(int(t[pos]) if lim else 9, limit)
ans = 0
for i in range(up + 1):
ans += dfs(pos + 1, lim and i == int(t[pos]))
return ans
n = len(s)
t = str(start - 1)
a = dfs(0, True)
dfs.cache_clear()
t = str(finish)
b = dfs(0, True)
return b - a
###java
class Solution {
private String s;
private String t;
private Long[] f;
private int limit;
public long numberOfPowerfulInt(long start, long finish, int limit, String s) {
this.s = s;
this.limit = limit;
t = String.valueOf(start - 1);
f = new Long[20];
long a = dfs(0, true);
t = String.valueOf(finish);
f = new Long[20];
long b = dfs(0, true);
return b - a;
}
private long dfs(int pos, boolean lim) {
if (t.length() < s.length()) {
return 0;
}
if (!lim && f[pos] != null) {
return f[pos];
}
if (t.length() - pos == s.length()) {
return lim ? (s.compareTo(t.substring(pos)) <= 0 ? 1 : 0) : 1;
}
int up = lim ? t.charAt(pos) - '0' : 9;
up = Math.min(up, limit);
long ans = 0;
for (int i = 0; i <= up; ++i) {
ans += dfs(pos + 1, lim && i == (t.charAt(pos) - '0'));
}
if (!lim) {
f[pos] = ans;
}
return ans;
}
}
###cpp
class Solution {
public:
long long numberOfPowerfulInt(long long start, long long finish, int limit, string s) {
string t = to_string(start - 1);
long long f[20];
memset(f, -1, sizeof(f));
auto dfs = [&](this auto&& dfs, int pos, int lim) -> long long {
if (t.size() < s.size()) {
return 0;
}
if (!lim && f[pos] != -1) {
return f[pos];
}
if (t.size() - pos == s.size()) {
return lim ? s <= t.substr(pos) : 1;
}
long long ans = 0;
int up = min(lim ? t[pos] - '0' : 9, limit);
for (int i = 0; i <= up; ++i) {
ans += dfs(pos + 1, lim && i == (t[pos] - '0'));
}
if (!lim) {
f[pos] = ans;
}
return ans;
};
long long a = dfs(0, true);
t = to_string(finish);
memset(f, -1, sizeof(f));
long long b = dfs(0, true);
return b - a;
}
};
###go
func numberOfPowerfulInt(start, finish int64, limit int, s string) int64 {
t := strconv.FormatInt(start-1, 10)
f := make([]int64, 20)
for i := range f {
f[i] = -1
}
var dfs func(int, bool) int64
dfs = func(pos int, lim bool) int64 {
if len(t) < len(s) {
return 0
}
if !lim && f[pos] != -1 {
return f[pos]
}
if len(t)-pos == len(s) {
if lim {
if s <= t[pos:] {
return 1
}
return 0
}
return 1
}
ans := int64(0)
up := 9
if lim {
up = int(t[pos] - '0')
}
up = min(up, limit)
for i := 0; i <= up; i++ {
ans += dfs(pos+1, lim && i == int(t[pos]-'0'))
}
if !lim {
f[pos] = ans
}
return ans
}
a := dfs(0, true)
t = strconv.FormatInt(finish, 10)
for i := range f {
f[i] = -1
}
b := dfs(0, true)
return b - a
}
###ts
function numberOfPowerfulInt(start: number, finish: number, limit: number, s: string): number {
let t: string = (start - 1).toString();
let f: number[] = Array(20).fill(-1);
const dfs = (pos: number, lim: boolean): number => {
if (t.length < s.length) {
return 0;
}
if (!lim && f[pos] !== -1) {
return f[pos];
}
if (t.length - pos === s.length) {
if (lim) {
return s <= t.substring(pos) ? 1 : 0;
}
return 1;
}
let ans: number = 0;
const up: number = Math.min(lim ? +t[pos] : 9, limit);
for (let i = 0; i <= up; i++) {
ans += dfs(pos + 1, lim && i === +t[pos]);
}
if (!lim) {
f[pos] = ans;
}
return ans;
};
const a: number = dfs(0, true);
t = finish.toString();
f = Array(20).fill(-1);
const b: number = dfs(0, true);
return b - a;
}
###cs
public class Solution {
private string s;
private string t;
private long?[] f;
private int limit;
public long NumberOfPowerfulInt(long start, long finish, int limit, string s) {
this.s = s;
this.limit = limit;
t = (start - 1).ToString();
f = new long?[20];
long a = Dfs(0, true);
t = finish.ToString();
f = new long?[20];
long b = Dfs(0, true);
return b - a;
}
private long Dfs(int pos, bool lim) {
if (t.Length < s.Length) {
return 0;
}
if (!lim && f[pos].HasValue) {
return f[pos].Value;
}
if (t.Length - pos == s.Length) {
return lim ? (string.Compare(s, t.Substring(pos)) <= 0 ? 1 : 0) : 1;
}
int up = lim ? t[pos] - '0' : 9;
up = Math.Min(up, limit);
long ans = 0;
for (int i = 0; i <= up; ++i) {
ans += Dfs(pos + 1, lim && i == (t[pos] - '0'));
}
if (!lim) {
f[pos] = ans;
}
return ans;
}
}
时间复杂度 $O(\log M \times D)$，空间复杂度 $O(\log M)$，其中 $M$ 为数字的上限，而 $D = 10$。
有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~
