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。

自建示例

统计位数更短和同位数的数字:

输入:digits = ["1","3","5"], n = 400
输出:30
解释:一位数有 3 个,两位数有 3^2 = 9 个;三位数首位只能为 1 或 3,后两位各有 3 种选择,共 18 个。因此总数为 3 + 9 + 18 = 30。

上界小于最小可用数字:

输入:digits = ["4","7"], n = 3
输出:0
解释:最小能够组成的正整数是 4,已经大于 n,因此不存在符合条件的数字。