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. 给定一个1-9的集合S，和一个上限k
2. 求这个集合中能构成多少个数，并且不大于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;
    }
}

---

我们一直在努力

apachecn/AiLearning

---