题目描述：
给定一个按 非递减顺序 排列的数字数组 digits 。你可以用任意次数 digits[i] 来写的数字。例如，如果 digits = ['1','3','5']，我们可以写数字，如 '13', '551', 和 '1351315'。
返回 可以生成的小于或等于给定整数 n 的正整数的个数 。
数据范围：
$1\le digits.len \le 9, 1\le n \le 10^9$
题解：
这个题目好像不能忽略前导零了。因为 $digits$ 里面不包含 $0$ ，第一个位置可以填 $0$ ，其余的不能填 $0$ ，需要单独填一次 $0$ ，判断一下。而且纯 $0$ 是不能作为答案的。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
vector<int> num;
int len;
string s;
int dp[10];
int dfs(int step, bool isLimit, bool isLead)
{
if (step == len)
return !isLead;
if (!isLimit && !isLead && dp[step] != -1)
return dp[step];
int up = isLimit ? s[step] - '0' : 9;
int ans = 0;
if (isLead)
ans += dfs(step + 1, false, true);
for (int i = 0; i < num.size(); ++i)
{
if (num[i] > up)
break;
ans += dfs(step + 1, isLimit && num[i] == up, false);
}
if (!isLimit && !isLead)
dp[step] = ans;
return ans;
}
int atMostNGivenDigitSet(vector<string> &digits, int n)
{
s = to_string(n);
for (auto &ss : digits)
{
num.emplace_back(ss[0] - '0');
}
len = s.length();
memset(dp, -1, sizeof(dp));
return dfs(0, true, true);
}
};
|