5
最大为 N 的数字组合_安东尼漫长的技术岁月的技术博客_51CTO博客
source link: https://blog.51cto.com/u_13961087/5765048
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
最大为 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
输入：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入门题：
题目要求返回通过digits中的数字可以生成的<=正整数 n 的正整数个数
如：digits=["1","3"] n=52 答案是：1,3,11,13,31,3
将digits转化为int数组类型的nums
记nums的长度为M，f(x)为nums能组成的位于[1,x]的数字个数，正整数x的长度为N
我们可以大体将[1,x]的数字分为3个部分：
- 位数小于N的部分，这部分可通过计算得到，设此时数字的位数为k，那么这部分个数为 ∑M^k(k∈[1,N-1])（nums数字可以复用）
- 位数等于N的部分，且最高位比x最高位小，这部分也可通过计算得到，设r为nums在x对应位能取到的数字最大索引 那么x对应位可以取到digits[0,r]，后面任意取都不会超过x，因此这部分个数为 (r+1)*M^(N-p)，其中N-p表示当前位后面还有多少位数
- 位数等于N的部分，且最高位等于x最高位，最高位处保守只能取到digits[0,r-1]，这部分个数为 r*M^(N-p)
还没完，还要累加最高位为digits[r]的情况，这取决于后面数字的贡献数，参考下一位数属于哪种情况 最后答案就是f(n)
JS 实现：
/**
* @param {string[]} digits
* @param {number} n
* @return {number}
*/
var atMostNGivenDigitSet = function(digits, n) {
const s = n + '';
const K = s.length;
const dp = new Array(K+1).fill(0);
dp[K] = 1;
for(let i = K -1; i >= 0; --i) {
let si = s[i];
for(let j=0; j < digits.length; j++) {
if(digits[j] < si) {
dp[i] += Math.pow(digits.length, K-i-1)
} else if(digits[j] == si) {
dp[i] += dp[i+1];
}
}
}
for(let k=1; k< K; ++k) {
dp[0] += Math.pow(digits.length, k)
}
return dp[0]
};
* @param {string[]} digits
* @param {number} n
* @return {number}
*/
var atMostNGivenDigitSet = function(digits, n) {
const s = n + '';
const K = s.length;
const dp = new Array(K+1).fill(0);
dp[K] = 1;
for(let i = K -1; i >= 0; --i) {
let si = s[i];
for(let j=0; j < digits.length; j++) {
if(digits[j] < si) {
dp[i] += Math.pow(digits.length, K-i-1)
} else if(digits[j] == si) {
dp[i] += dp[i+1];
}
}
}
for(let k=1; k< K; ++k) {
dp[0] += Math.pow(digits.length, k)
}
return dp[0]
};
动态规划是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。
- 赞
- 收藏
- 1评论
- 分享
- 举报
上一篇：水果成篮问题
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK