0902. Numbers At Most N Given Digit Set ======================================== 题目信息 -------- :题号: 0902 :难度: Hard :主题: 数字构造、组合计数、前缀限制 :原题: `LeetCode 0902 `_ :重点: 给定数字字符可以重复使用;只统计不带前导零的正整数,并要求结果不大于 ``n`` 题目重述 -------- 给定按递增顺序排列、互不相同的数字字符数组 ``digits``,其中每个字符都在 ``"1"`` 至 ``"9"`` 之间;另给定正整数 ``n``。 可以从 ``digits`` 中任意选择字符组成正整数,同一个字符可以重复使用任意次。组成的数字不能带前导零。请返回所有数值小于或等于 ``n`` 的可组成正整数数量。 ``1 <= digits.length <= 9``,``1 <= n <= 10^9``。 自建示例 -------- 统计位数更短和同位数的数字: .. code-block:: text 输入:digits = ["1","3","5"], n = 400 输出:30 解释:一位数有 3 个,两位数有 3^2 = 9 个;三位数首位只能为 1 或 3,后两位各有 3 种选择,共 18 个。因此总数为 3 + 9 + 18 = 30。 上界小于最小可用数字: .. code-block:: text 输入:digits = ["4","7"], n = 3 输出:0 解释:最小能够组成的正整数是 4,已经大于 n,因此不存在符合条件的数字。