题目:902. 最大为 N 的数字组合
难度:困难
给定一个按 非递减顺序 排列的数字数组 digits 。你可以用任意次数 digits[i] 来写的数字。例如,如果 digits = [‘1’,‘3’,‘5’],我们可以写数字,如 ‘13’, ‘551’, 和 ‘1351315’。
返回 可以生成的小于或等于给定整数 n 的正整数的个数 。
示例 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:
输入:digits = [“1”,“4”,“9”], n = 1000000000
输出:29523
解释: 我们可以写 3 个一位数字,9个两位数字,27 个三位数字, 81 个四位数字,243 个五位数字,729 个六位数字, 2187 个七位数字,6561 个八位数字和19683 个九位数字。 总共,可以使用D中的数字写出 29523 个整数。
示例 3:
输入:digits = [“7”], n = 8
输出:1
提示:
1 <= digits.length <= 9
digits[i].length == 1
digits[i] 是从 ‘1’ 到 ‘9’ 的数
digits 中的所有值都 不同
digits 按 非递减顺序 排列
1 <= n <= 109
数位dp:
定义状态:我们用 dp[i][0]表示由 digits构成且小于n 的前 i 位的数字的个数,dp[i][1] 表示由 digits构成且等于 n 的前 i 位的数字的个数,可知 dp[i][1] 的取值只能为0 和 1。
n表示给定数字最大值,d表示digits中的数字,n的前i位组成的数字为n[i],这里会遇到几种情况:
1、当i>1时,任意digits中的d都小于等于s[:i],这一情况下满足条件的数量为len(digits)
2、当d
我们初始将dp[0][1]设为1,遍历到后面如果发现digits中不含有某个n[i],再将dp[i][1]设置为1
设 C[i]表示数组 digits 中小于 n 的第 i 位数字的元素个数,综上所述,dp的状态转移方程为:
class Solution:
def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:
m = len(digits)
s = str(n)
k = len(s)
dp = [[0, 0] for _ in range(k + 1)]
# 设置初始状态
dp[0][1] = 1
# 遍历n
for i in range(1, k + 1):
# 遍历digits
for d in digits:
# digits中存在n[i]
if d == s[i - 1]:
dp[i][1] = dp[i - 1][1]
# d小于n[i-1],累加上dp[i-1][1],属于当d=n[i-1],我必须向后加一个小于n[i]的才满足条件的情况
elif d < s[i - 1]:
dp[i][0] += dp[i - 1][1]
else:
break
# 当i>1,累加上所有情况即可
if i > 1:
dp[i][0] += m + dp[i - 1][0] * m
# 返回最后一位dp[k][0]和dp[k][1]的和即可
return sum(dp[k])