图解LeetCode——902. 最大为 N 的数字组合（难度：困难）

一、题目

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

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

二、示例

2.1> 示例 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.2> 示例 2：

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

2.3> 示例 3:

【输入】digits = ["7"], n = 8 【输出】1

提示：

• • 1 <= digits.length <= 9
• • digits[i].length == 1
• • digits[i] 是从 '1' 到 '9' 的数
• • digits 中的所有值都 **不同 **
• • digits 按 非递减顺序 排列
• • 1 <= n <= 10^9

三、解题思路

首先，根据题意，我们要计算出通过digits数组中数字的组合，可以生成的小于或等于给定整数n的正整数的个数。那么，我们可以根据两种情况进行分析：

【情况1】n的最高位不等于digits数组中任意数字。 【情况2】n的最高位等于digits数组中的某个数字。

针对于【情况1】，我们以digits = ["1","3","5","7"], n = 8321为例。由于n的最高位是8，它不在digits数组中，并且比任意一个digits数组中的数字都大，那么我们可以得出如下结论：

第1位（8） 可以拼装出的组合数量为：4^4种 第2位（3） 可以拼装出的组合数量为：4^3种 第3位（2） 可以拼装出的组合数量为：4^2种 第4位（1） 可以拼装出的组合数量为：4^1种

我们将这4位的每个组合种类数量进行相加，最终结果就是：4^4 + 4^3 + 4^2 + 4^1 = 340种。具体操作，如下图所示：

针对于【情况2】，我们以digits = ["1","3","5","7"], n = 5321为例。由于n的第1位是5，它并没有大于digits中的所有数字，所以，最高位的拼装数量就一定小于4^4。但是，对于后3位数字的拼装，是没有影响的，所以我们分为两个步骤进行统计：

【步骤1】首先：计算后3位拼装组合，即：4^3 + 4^2 + 4^1 = 84种 【步骤2】然后：计算第1位拼装组合，我们下面再具体分析计算。

由于n的第1位是5，它大于digits数组里的“1”和“3”，所以，针对第1位如果是“1”或“3”的话，最高位可以拼装的组合都是4^3种。

由于n的第1位是5，它等于digits数组里的“5”，针对这种情况，我们就需要再继续看它的下一位数字，即：n的第2位——数字3。

由于n的第2位是3，它大于digits数组里的“1”，所以，针对第2位如果是“1”的话，可以拼装的组合都是4^2种。

由于n的第2位是3，它等于digits数组里的“3”，针对这种情况，我们就需要再继续看它的下一位数字，即：n的第3位——数字2。下面的操作以此类推，整体的操作请参见下图所示，此处就不再赘述了：

四、代码实现

class Solution {
    public int atMostNGivenDigitSet(String[] digits, int n) {
        char[] nc = String.valueOf(n).toCharArray();
        int result = 0, ncl = nc.length, dl = digits.length;
        for (int i = 1; i < ncl; i++) result += Math.pow(dl, i); // 先对【非最高位】的其他位，可组装的数字进行统计
        for (int i = 0; i < ncl; i++) {
            boolean compareNext = false; // 是否需要对比下一个数字
            for (String digit : digits) {
                char dc = digit.charAt(0); // 将String转换为char
                if (dc < nc[i]) result += Math.pow(dl, ncl - i - 1);
                else {
                    if (dc == nc[i]) compareNext = true; break;
                }
            }
            if (!compareNext) return result;
        }
        return ++result; // 如果到最后1位依然满足compareNext，因为最后1位无法再向后对比了，所以最终结果+1
    }
}