从0开始的秋招刷题路，记录下所刷每道题的题解，帮助自己回顾总结
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 <=
1
0
9
10^9
109
解题思路
一眼看过去，数学题，排列组合嘛。
老样子先自己构造两个测试数据： D = [“3”,“4”,“6”,“7”] N = 75134
很显然，对于一个 5 位数的 N 来说，所有 4/3/2/1 位数的数字都一定小于它
这也是最好计算的部分，每一位都有 4 个数字可以选择，也就是分别有 4⁴ , 4³ , 4² , 4¹ 种情况。
而 5 位数的情况，就相对复杂了许多，需要多考虑点了：
如上图所示，5 位数的话，假如第一位比 7 小，那么后面四位其实就没所谓大小了。
此时组合的数量就是 第一位的情况数量 f(7) * 4⁴，后四位的情况，恰好对应了只有四位数的时候。
但是如果第一位恰好等于 7 呢？那就只能要求第二位小于 5 了，最后那三位可以随意。
以此类推，直到五位数每一位都等于相应的数字，那就只有一种情况了。
图中在每一种组合后面，标注了相应的数量。
但是，仔细观察一下我们提供的数组 D ，里面压根没有 5, 1这两个数字啊：
如上图所示，红色表示并不存在的数字，可以看到由于 5的影响，其实后面的几种情况已经全都不用计算了，压根不会出现。
那么思路就已经比较清晰了，和目标数字相等长度的数字需要遍历查找，其它数字可以直接计算得出来。文章来源：https://www.toymoban.com/news/detail-433984.html
代码文章来源地址https://www.toymoban.com/news/detail-433984.html
class Solution {
public int atMostNGivenDigitSet(String[] D, int N) {
int ans = 0;
// 对 D 数组进行预处理
int[] less_than_d = new int[10];
int[] d_arr = new int[10];
for (int i = 0; i < D.length; i++) {
Arrays.fill(less_than_d, Integer.parseInt(D[i]) + 1, 10, i + 1);
d_arr[Integer.parseInt(D[i])] = 1;
}
// 一位数的 N 可以直接返回
if (N / 10 == 0)
return less_than_d[N] + d_arr[N];
// 将 N 打平存入数组
int n_len = 0;
int[] n_arr = new int[10];
while (N != 0) {
n_arr[n_len] = N % 10;
n_len += 1;
N = N / 10;
}
// 把各种幂算出来备用，n_pow[2] 里存的是平方
int[] n_pow = new int[n_len];
n_pow[0] = 1;
for (int i = 1; i < n_len; i++)
ans += (n_pow[i] = D.length * n_pow[i - 1]);
// 将所有可能性加起来
ans += less_than_d[n_arr[n_len - 1]] * n_pow[n_len - 1];
for (int i = n_len - 1; i >= 0; i--)
if (d_arr[n_arr[i]] == 1)
ans = i == 0 ? ans + 1 : ans + less_than_d[n_arr[i - 1]] * n_pow[i - 1];
else
break;
return ans;
}
}
到了这里，关于Leetcode力扣秋招刷题路-0902的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
