0902. Numbers At Most N Given Digit Set¶
题目信息¶
- 题号:
0902
- 难度:
Hard
- 主题:
数字构造、组合计数、前缀限制
- 原题:
- 重点:
给定数字字符可以重复使用;只统计不带前导零的正整数,并要求结果不大于
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,因此不存在符合条件的数字。