902. 最大为 N 的数字组合

我们有一组排序的数字 D，它是 {'1','2','3','4','5','6','7','8','9'} 的非空子集。（请注意，'0' 不包括在内。）
现在，我们用这些数字进行组合写数字，想用多少次就用多少次。例如 D = {'1','3','5'}，我们可以写出像 '13', '551', '1351315' 这样的数字。
返回可以用 D 中的数字写出的小于或等于 N 的正整数的数目。

示例 1：
输入：D = [“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：
输入：D = [“1”,”4”,”9”], N = 1000000000
输出：29523
解释：
我们可以写 3 个一位数字，9 个两位数字，27 个三位数字，
81 个四位数字，243 个五位数字，729 个六位数字，
2187 个七位数字，6561 个八位数字和 19683 个九位数字。
总共，可以使用D中的数字写出 29523 个整数。

提示：

  1. D 是按排序顺序的数字 '1'-'9' 的子集。
  2. 1 <= N <= 10^9

思路：
递推型写法：

  1. 先预处理N，抠出每一位十进制数，假设共有n位
  2. n - 1位数一定都小于N，每一位能选的个数有D.length个，用循环处理一下
  3. 从最高位向最低位依次考虑，只有对应位在D中存在才会继续向低位考虑。
  1. class Solution {
  2.     public int atMostNGivenDigitSet(String[] digits, int v) {
  3.         String num = Integer.toString(v);
  4.         int n = digits.length, res = 0;
  6.         for (int i = 1; i < num.length(); i++) {
  7.             res += power(n, i);
  8.         }
  10.         boolean flag = true;
  11.         for (int i = 0; i < num.length(); i++) {
  12.             int x = num.charAt(i) - '0';
  13.             int cnt = power(n, num.length() - 1 - i);
  14.             int j = 0;
  15.             while (j < n && digits[j].charAt(0) - '0' < x) {
  16.                 res += cnt;
  17.                 j++;
  18.             }
  19.             if (j < n && digits[j].charAt(0) - '0' == x)
  20.                 continue;
  21.             else {
  22.                 flag = false;
  23.                 break;
  24.             }
  25.         }
  26.         if (flag)
  27.             res++;
  28.         return res;
  29.     }
  30.     int power(int a, int b) {
  31.         int res = 1;
  32.         while (b > 0) {
  33.             if ((b & 1) == 1)
  34.                 res *= a;
  35.             a *= a;
  36.             b >>= 1;
  37.         }
  38.         return res;
  39.     }
  40. }

记忆化搜索：
模板：
pos表示当前枚举到第几位，从高位向低位枚举，假设最低位为第0位
lim表示高位的数是否贴合上界，1表示贴合上界
lead表示高位是否全为0，1表示高位全为0

  1. class Solution {
  2.     List<Integer> list = new ArrayList<>();
  3.     List<Integer> num = new ArrayList<>();
  4.     int[] f = new int[10];
  5.     public int atMostNGivenDigitSet(String[] digits, int n) {
  6.         for (String s : digits) {
  7.             list.add(Integer.parseInt(s));
  8.         }
  9.         while (n > 0) {
  10.             num.add(n % 10);
  11.             n /= 10;
  12.         }
  13.         Arrays.fill(f, -1);
  14.         return dp(num.size() - 1, 1, 1); 
  15.     }
  17.     int dp(int cur, int lim, int lead) {
  18.         if (cur == -1)
  19.             return lead == 0 ? 1 : 0;
  20.         int ans = f[cur];
  21.         if (lim != 1 && lead != 1 && ans != -1) return ans;
  23.         ans = 0;
  24.         int up = lim == 1 ? num.get(cur) : 9;
  25.         if (lead == 1) ans += dp(cur - 1, 0, 1);
  26.         for (int i : list) {
  27.             if (i > up) break;
  28.             if (lim == 1 && i == up)
  29.                 ans += dp(cur - 1, 1, 0);
  30.             else ans += dp(cur - 1, 0, 0);
  31.         }
  32.         if (lim != 1 && lead != 1) f[cur] = ans;
  33.         return ans;
  34.     }
  35. }