leetcode 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/记忆化搜索,C++ 0ms
思路
我们通过几个简单的子问题来解决这道题。
- 去掉
<=n
的条件,只是求位数为k的满足条件的数,怎样求解?显然,由于大小不限而且digits中没有0,每一位都有digits.size()
种选择,那么,总共就有digits.size()^k
个数(排列组合/乘法原理)。 - 加入
<=n
的限制,变为求位数与n相同的<=n的数,如果第一位已经确定- 假如第一位严格小于n的第一位,那么,后面的几位又不受限制了,这样,相当于求位数为k-1的由
digits
组成的数。根据上面的结论,就应当是digits.size()^(k-1)
。 - 假如第一位严格大于n的第一位,那么,无论后面怎么排列,都不能产生
<n
的数了,答案就是0。 - 假如第一位
==n的第一位
,那么,要求从第二位开始的数<=n从第二位开始的数。这就产生了递归。
- 假如第一位严格小于n的第一位,那么,后面的几位又不受限制了,这样,相当于求位数为k-1的由
根据上面的推断,有这样的思路:设n的位数为cnt,位数为1~cnt-1
的数的个数可以直接求出,也就是digits.size()^k
,由于后面要经常用到,我们将它记忆下来,作为一个memo数组。那么,我们只需要求位数为cnt的<=n的由digits组成的数了。根据上面的推断,我们编写递归函数dfs,对于每一位,遍历digits,如果小于limit[k],直接加上memo[k],如果等于limit[k],搜索下一位,如果大于,就是0。
具体细节(位数的对应关系)可以看一下这张图,这是在digits=[1,4,7],n=12345
时生成的limit
和memo
数组。
为了方便写,我传入的是第k位数(从1开始),并找到limit和memo中对应的位置比较即可,这里不多讲了。
记忆化搜索写法
1 | class Solution { |
动态规划写法
将自前往后搜索改为自后往前记录,可以将记忆化搜索改成动态规划,这两者时空复杂度相同,代码也高度相似,就不多说了。
1 | class Solution { |
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 HeRen's Blog!
评论