题目简介

902. 最大为 N 的数字组合

难度：困难

给定一个按 非递减顺序 排列的数字数组 digits 。你可以用任意次数 digits[i] 来写的数字。例如，如果 digits = [‘1’,’3’,’5’]，我们可以写数字，如 ‘13’, ‘551’, 和 ‘1351315’。

返回 可以生成的小于或等于给定整数 n 的正整数的个数 。

示例 1：

1
2
3
4
5
输入：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：

1
2
3
4
5
6
7
输入：digits = ["1","4","9"], n = 1000000000
输出：29523
解释：
我们可以写 3 个一位数字，9 个两位数字，27 个三位数字，
81 个四位数字，243 个五位数字，729 个六位数字，
2187 个七位数字，6561 个八位数字和 19683 个九位数字。
总共，可以使用D中的数字写出 29523 个整数。

示例 3:

1
2
输入：digits = ["7"], n = 8
输出：1

解法

时间与内存情况：

1.png

设数字n的长度（严谨的表述应该为将n转化为切片后n的长度）为ln，切片digits的长度为ld。答案设为res。

此题笔者一开始并没有想到官方解法中的数位动态规划。而是注意到了在到达n的长度之前的情况（如示例2，n为十位长度的数，则在长度为1到9位的情况下）res只需要简单的加上ld的1次方，2次方，一直到ln-1次方即可。

而在与n的长度相等时，则需要比较最高位与digits中的数字大小：

  1. 如果digits中数字小于当前最高位，则res只需加上ld的当前数字长度减1次方。
  2. 如果digits中数字大于当前最高位，则选取这个数字后，后面再加任何数都不符合题意，所以直接忽略掉这种情况即可。
  3. 如果digits中数字等于当前最高位，那么我们需要判断截掉当前最高位后剩下的数有多少情况满足题意。也就是说，将n去掉最高位后的数再按照上述流程走一遍。（即递归）

代码如下，因为Go语言中没有针对int类型的指数内置函数，所以只能自己实现一个（这是个Go非常不友好的地方，开发人员解释的原因是int类型的此类函数用户可以轻易实现，而float64类型大部分人实现有难度，所以只提供了float64类型的。笔者并不赞成此解释）。最后两个函数大家可以略过不看：

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
func atMostNGivenDigitSet(digits []string, n int) int {
    n_s := strconv.Itoa(n)
    ln, ld := len(n_s), len(digits)
    res := 0
    res += exp_sum(ld, ln - 1)
    res += recursion(digits, []byte(n_s))
    return res
}

func recursion(digits []string, d []byte) (ans int) {
    if len(d) == 0 {
        return 1
    }
    n_less, ans := 0, 0
    for _, digit := range digits {
        if digit < string(d[0]) {
            n_less += 1
        } else if digit == string(d[0]) {
            ans += recursion(digits, d[1:])
        }
    }
    ans += n_less * exp(len(digits), len(d)-1)
    return ans
}

func exp_sum(a, b int) int {
    last, r := 1, 0
    for i := 0; i < b; i++ {
        last *= a
        r += last
    }
    return r
}

func exp(a, b int) int {
    r := 1
    for i := 0; i < b; i++ {
        r *= a
    }
    return r
}

由于笔者在审题时没有看到数字数组是 非递减顺序 排列，所以没有针对此情况优化。得益于Go强大的效率，此代码执行用时依然是0ms。读者可以自己尝试优化一下。