最大为 N 的数字组合

Given an array of digits which is sorted in non-decreasing order. You can write numbers using each digits[i] as many times as we want. For example, if digits = ['1','3','5'], we may write numbers such as '13', '551', and '1351315'.

Return the number of positive integers that can be generated that are less than or equal to a given integer n.

 

Example 1:

Input: digits = ["1","3","5","7"], n = 100
Output: 20
Explanation: 
The 20 numbers that can be written are:
1, 3, 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77.

Example 2:

Input: digits = ["1","4","9"], n = 1000000000
Output: 29523
Explanation: 
We can write 3 one digit numbers, 9 two digit numbers, 27 three digit numbers,
81 four digit numbers, 243 five digit numbers, 729 six digit numbers,
2187 seven digit numbers, 6561 eight digit numbers, and 19683 nine digit numbers.
In total, this is 29523 integers that can be written using the digits array.

Example 3:

Input: digits = ["7"], n = 8
Output: 1

 

Constraints:

• 1 <= digits.length <= 9
• digits[i].length == 1
• digits[i] is a digit from '1' to '9'.
• All the values in digits are unique.
• digits is sorted in non-decreasing order.
• 1 <= n <= 109

/*
 * 思路：
 * 1. 先将目标数n转换为字符串，以便逐位比较。
 * 2. 使用递归方法生成所有可能的小于或等于n的数字组合。
 * 3. 递归方法中每次尝试在当前数字后面添加一个新数字，若新数字大于n则停止递归。
 * 4. 使用Java Stream进行递归遍历。
 */
import java.util.*;

public class Solution {
    public int atMostNGivenDigitSet(String[] digits, int n) {
        String nStr = String.valueOf(n);
        return countNumbers(Arrays.stream(digits), nStr, true);
    }

    private int countNumbers(Stream<String> digitStream, String nStr, boolean isPrefix) {
        int count = isPrefix ? 0 : 1;
        if (nStr.isEmpty()) {
            return count;
        }
        List<String> digits = digitStream.toList();
        count += digits.stream()
            .mapToInt(digit -> {
                if (digit.charAt(0) < nStr.charAt(0)) {
                    return (int) Math.pow(digits.size(), nStr.length() - 1);
                } else if (digit.charAt(0) == nStr.charAt(0)) {
                    return countNumbers(digits.stream(), nStr.substring(1), true);
                } else {
                    return 0;
                }
            })
            .sum();
        return count;
    }
}

这个解法使用动态规划来计算能生成的小于或等于n的数字的个数。首先，将n转换为字符串S以便逐位比较。创建一个dp数组，其中dp[i]表示使用digits中的数字，生成的数字小于S的第i位到最后一位的子字符串。遍历每一位数字，比较digits中的每个元素与S的当前位。如果digit小于S的当前位，则可以自由地选择剩余的位，其个数是len(digits)的(K-i-1)次幂。如果digit等于S的当前位，则当前位固定，剩余位的选择数等于dp[i+1]。最终，dp[0]加上所有小于K位数的组合数给出答案。

O(K * len(digits))

O(K)