| comments | difficulty | edit_url | tags | |||||
|---|---|---|---|---|---|---|---|---|
true |
困难 |
|
给定一个按 非递减顺序 排列的数字数组 digits 。你可以用任意次数 digits[i] 来写的数字。例如，如果 digits = ['1','3','5']，我们可以写数字，如 '13', '551', 和 '1351315'。
返回 可以生成的小于或等于给定整数 n 的正整数的个数 。
示例 1：
输入：digits = ["1","3","5","7"], n = 100 输出：20 解释： 可写出的 20 个数字是： 1, 3, 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77.
示例 2：
输入：digits = ["1","4","9"], n = 1000000000 输出：29523 解释： 我们可以写 3 个一位数字，9 个两位数字，27 个三位数字， 81 个四位数字，243 个五位数字，729 个六位数字， 2187 个七位数字，6561 个八位数字和 19683 个九位数字。 总共，可以使用D中的数字写出 29523 个整数。
示例 3:
输入：digits = ["7"], n = 8 输出：1
提示：
1 <= digits.length <= 9digits[i].length == 1digits[i]是从'1'到'9'的数digits中的所有值都 不同digits按 非递减顺序 排列1 <= n <= 109
这道题实际上是求在给定区间 digits 中的数字生成的正整数的个数。个数与数的位数以及每一位上的数字有关。我们可以用数位 DP 的思路来解决这道题。数位 DP 中，数的大小对复杂度的影响很小。
对于区间
不过对于本题而言，我们只需要求出区间
这里我们用记忆化搜索来实现数位 DP。从起点向下搜索，到最底层得到方案数，一层层向上返回答案并累加，最后从搜索起点得到最终的答案。
基本步骤如下：
- 将数字
$n$ 转为 int 数组$a$ ，其中$a[1]$ 为最低位，而$a[len]$ 为最高位； - 根据题目信息，设计函数
$dfs()$ ，对于本题，我们定义$dfs(pos, lead, limit)$ ，答案为$dfs(len, 1, true)$ 。
其中：
-
pos表示数字的位数，从末位或者第一位开始，一般根据题目的数字构造性质来选择顺序。对于本题，我们选择从高位开始，因此，pos的初始值为len； -
lead表示当前数字中是否包含前导零，如果包含，则为1，否则为0；初始化为1； -
limit表示可填的数字的限制，如果无限制，那么可以选择$[0,1,..9]$ ，否则，只能选择$[0,..a[pos]]$ 。如果limit为true且已经取到了能取到的最大值，那么下一个limit同样为true；如果limit为true但是还没有取到最大值，或者limit为false，那么下一个limit为false。
关于函数的实现细节，可以参考下面的代码。
时间复杂度
相似题目：
class Solution:
def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:
@cache
def dfs(pos, lead, limit):
if pos <= 0:
return lead == False
up = a[pos] if limit else 9
ans = 0
for i in range(up + 1):
if i == 0 and lead:
ans += dfs(pos - 1, lead, limit and i == up)
elif i in s:
ans += dfs(pos - 1, False, limit and i == up)
return ans
l = 0
a = [0] * 12
s = {int(d) for d in digits}
while n:
l += 1
a[l] = n % 10
n //= 10
return dfs(l, True, True)class Solution {
private int[] a = new int[12];
private int[][] dp = new int[12][2];
private Set<Integer> s = new HashSet<>();
public int atMostNGivenDigitSet(String[] digits, int n) {
for (var e : dp) {
Arrays.fill(e, -1);
}
for (String d : digits) {
s.add(Integer.parseInt(d));
}
int len = 0;
while (n > 0) {
a[++len] = n % 10;
n /= 10;
}
return dfs(len, 1, true);
}
private int dfs(int pos, int lead, boolean limit) {
if (pos <= 0) {
return lead ^ 1;
}
if (!limit && lead != 1 && dp[pos][lead] != -1) {
return dp[pos][lead];
}
int ans = 0;
int up = limit ? a[pos] : 9;
for (int i = 0; i <= up; ++i) {
if (i == 0 && lead == 1) {
ans += dfs(pos - 1, lead, limit && i == up);
} else if (s.contains(i)) {
ans += dfs(pos - 1, 0, limit && i == up);
}
}
if (!limit && lead == 0) {
dp[pos][lead] = ans;
}
return ans;
}
}class Solution {
public:
int a[12];
int dp[12][2];
unordered_set<int> s;
int atMostNGivenDigitSet(vector<string>& digits, int n) {
memset(dp, -1, sizeof dp);
for (auto& d : digits) {
s.insert(stoi(d));
}
int len = 0;
while (n) {
a[++len] = n % 10;
n /= 10;
}
return dfs(len, 1, true);
}
int dfs(int pos, int lead, bool limit) {
if (pos <= 0) {
return lead ^ 1;
}
if (!limit && !lead && dp[pos][lead] != -1) {
return dp[pos][lead];
}
int ans = 0;
int up = limit ? a[pos] : 9;
for (int i = 0; i <= up; ++i) {
if (i == 0 && lead) {
ans += dfs(pos - 1, lead, limit && i == up);
} else if (s.count(i)) {
ans += dfs(pos - 1, 0, limit && i == up);
}
}
if (!limit && !lead) {
dp[pos][lead] = ans;
}
return ans;
}
};func atMostNGivenDigitSet(digits []string, n int) int {
s := map[int]bool{}
for _, d := range digits {
i, _ := strconv.Atoi(d)
s[i] = true
}
a := make([]int, 12)
dp := make([][2]int, 12)
for i := range a {
dp[i] = [2]int{-1, -1}
}
l := 0
for n > 0 {
l++
a[l] = n % 10
n /= 10
}
var dfs func(int, int, bool) int
dfs = func(pos, lead int, limit bool) int {
if pos <= 0 {
return lead ^ 1
}
if !limit && lead == 0 && dp[pos][lead] != -1 {
return dp[pos][lead]
}
up := 9
if limit {
up = a[pos]
}
ans := 0
for i := 0; i <= up; i++ {
if i == 0 && lead == 1 {
ans += dfs(pos-1, lead, limit && i == up)
} else if s[i] {
ans += dfs(pos-1, 0, limit && i == up)
}
}
if !limit {
dp[pos][lead] = ans
}
return ans
}
return dfs(l, 1, true)
}