902. Numbers At Most N Given Digit Set
902. Numbers At Most N Given Digit Set
题目: https://leetcode.com/problems/numbers-at-most-n-given-digit-set/
难度: Hard
题意:
- 给定一个1-9的集合S,和一个上限k
- 求这个集合中能构成多少个数,并且不大于k
思路:
- 分情况计算
- 当构成的数的位数小于k的位数,那么能构成的数数量为|S|^位数
- 当构成的数的位数等于k的位数,遍历集合S的数a,判断a
- 如果小于k的最高位,那么能够成的数数量为|S|^(k的位数-1)
- 如果等于k的最高位,继续判断下一位
- 如果不存在等于k的最高位的数,不判断下一位,直接跳出循环
代码:
class Solution {
private int[] split(int a) {
int[] ret = new int[10];
int idx = 0;
while (a != 0) {
ret[idx++] = a % 10;
a /= 10;
}
return Arrays.copyOf(ret, idx);
}
public int atMostNGivenDigitSet(String[] D, int N) {
int[] d = new int[D.length];
for (int i = 0;i < D.length;i++) {
d[i] = Integer.parseInt(D[i]);
}
int[] length = new int[10];
length[0] = 1;
for (int i = 1;i < 10;i++) {
length[i] = length[i - 1] * D.length;
}
int[] a = split(N);
int ret = 0;
for (int i = 1;i < a.length;i++) {
ret += length[i];
}
int i;
for (i = a.length - 1;i >= 0;i--) {
boolean find = false;
for (int j = 0;j < d.length;j++) {
if (a[i] == d[j]) {
find = true;
}
if (d[j] < a[i]) {
ret += length[i];
}
}
if (!find) {
break;
}
}
if (i < 0) {
ret++;
}
return ret;
}
}