给定一个按 非递减顺序 排列的数字数组 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 <= 9digits[i].length == 1digits[i]是从'1'到'9'的数digits中的所有值都 不同digits按 非递减顺序 排列1 <= n <= 109
数学方法+递归，10月18日，今天的每日一题，有空偷个闲撸一把
看到题目第一反应是动态规划，然后扫了下题目给了示例，看到这么一段
输入：digits = ["1","4","9"], n = 1000000000
输出：29523
解释：
我们可以写 3 个一位数字，9 个两位数字，27 个三位数字，
81 个四位数字，243 个五位数字，729 个六位数字，
2187 个七位数字，6561 个八位数字和 19683 个九位数字。
总共，可以使用D中的数字写出 29523 个整数。突然灵光一闪，可以直接用数学方法来解
拿其中的一个示例稍微改下来分解运算试试看，粗略的分解如下
输入：digits = ["1","3","5","7"], n = 1571 1 5 7 1
4
16 4*4
64 4*4*4
45 0*4*4*4 + 1 * (2*4*4 + 1 * (3*4 + 1*( 0 + 1*(1))))最终验证得到 4 + 16 + 64 + 45 = 129 确定正确
如果你能看懂上面最后一行 4位数的组合数量计算公式的话，那么说明你就已经GET到了
数字1571一共有4位，那么我们将结果分为两部分，不满足4位的和满足4位的结果分开计算
在不满足4位的部分
- 如果只列举一位，那么就有
String[] digits种方案，每一个数字都可以列举一次 - 如果要列举两位数字的情况，那么每一位都可以列举
String[] digits种方案，在本示例中即为4 * 4种 - 如果要列举三位数字的话，那么同理有
4 * 4 * 4中，因为位数小于目标数字n = 1571的4位，所以可以任意组合，不要考虑结果是否会大于1571
接下来第二部分，需要组合4位数字的情况
- 我们先取出目标数字
1571的第一位数字1,拿到digits数组中比较，发现小于1的没有，但是有等于1的情况 - 如果
digits中存在小于当前位数字的lessCnt个，那么后面的排列组合可以不考虑。即有lessCnt * digits.length * ...... * digits.length种组合情况 - 如果
digits中没有当前位的数字，在处理了上一位小于的情况之后，说明后面无论怎么样排序都不会有满足结果小于目标值的情况 - 如果存在有等于当前位的数字，那么，我们需要再往后看一位，此时回到了和步骤1相同的处理逻辑部分
- 那么第二位是5，
digits数组中有[1,3]是小于5的，即可以有两种情况，后面无论如何排列都是满足的，那么得到2 * 4 * 4 - 又
digits数组中也包含了5，我们继续看下一位数字7 digits数组中有[1,3,5]小于7，于是有新的可能组合数量3 * 4，且数组中有数字7，那么继续看下一位数字- 最后一位数字1，同样的，数组中小于1的数字不存在，那么即有
0种情况，后面没有4要乘了 - 同时数组中包含了1，所以继续看下一位
- 最后已经没有下一位了，这里需要返回个1，根据前一步的结果返回0的话显然会造成结果不正确
代码
class Solution {
public int atMostNGivenDigitSet(String[] digits, int n) {
int size = getSize(n);
int ans = 0;
int t = digits.length;
//低位数的直接相加
while (--size>0){
ans += t;
t *= digits.length;
}
int[] intDigtis = getIntDigtis(digits);
int[] nArr = getNArr(n);
//最高位数的分区段统计数量
ans += splitCnt(intDigtis,nArr, 0);
return ans;
}
int splitCnt(int[] digits, int[] arr, int idx){
if (idx == arr.length){
return 1;
}
//比arr[idx]小的数字有个lessCnt个，相等的有equalCnt个
int lessCnt = 0;
int equalCnt = 0;
for (int i = 0; i < digits.length; i++) {
if (digits[i] > arr[idx]){
break;
}
if (digits[i] < arr[idx]){
lessCnt++;
}
if (digits[i] == arr[idx]){
equalCnt++;
}
}
for (int i = idx+1; i < arr.length; i++) {
lessCnt *= digits.length;
}
return lessCnt + (equalCnt * splitCnt(digits,arr,idx+1));
}
final static int[] mod = {
0,
1,
10,
100,
1000,
10000,
100000,
1000000,
10000000,
100000000,
1000000000
};
final static int [] sizeTable = {
9,
99,
999,
9999,
99999,
999999,
9999999,
99999999,
999999999,
Integer.MAX_VALUE
};
static int getSize(int x) {
for (int i=0; ; i++)
if (x <= sizeTable[i])
return i+1;
}
int[] getIntDigtis(String[] digtis) {
int[] intDigtis = new int[digtis.length];
for (int i = 0; i < digtis.length; i++) {
intDigtis[i] = digtis[i].charAt(0)-'0';
}
return intDigtis;
}
int[] getNArr(int n){
int size = getSize(n);
int[] nArr = new int[size];
int i = size;
while (n > 0){
nArr[size-i] = n/mod[i];
n %= mod[i];
i--;
}
return nArr;
}
}思路想明白了的话，还是不算太复杂的，主要是全位数部分计算的方法要递归起来实现的话，略微有点点显得绕
发表评论