class084 数位dp-上【算法】

package class084;
// 统计各位数字都不同的数字个数
// 给你一个整数n，代表十进制数字最多有n位
// 如果某个数字，每一位都不同，那么这个数字叫做有效数字
// 返回有效数字的个数，不统计负数范围
// 测试链接 : https://leetcode.cn/problems/count-numbers-with-unique-digits/
public class Code01_CountNumbersWithUniqueDigits {
  public static int countNumbersWithUniqueDigits(int n) {
    if (n == 0) {
      return 1;
    }
    int ans = 10;
    // 1 : 10
    // 2 : 9 * 9
    // 3 : 9 * 9 * 8
    // 4 : 9 * 9 * 8 * 7
    // ...都累加起来...
    for (int s = 9, i = 9, k = 2; k <= n; i--, k++) {
      s *= i;
      ans += s;
    }
    return ans;
  }
}

package class084;
// 最大为N的数字组合
// 给定一个按 非递减顺序 排列的数字数组 digits
// 已知digits一定不包含'0'，可能包含'1' ~ '9'，且无重复字符
// 你可以用任意次数 digits[i] 来写的数字
// 例如，如果 digits = ['1','3','5']
// 我们可以写数字，如 '13', '551', 和 '1351315'
// 返回 可以生成的小于或等于给定整数 n 的正整数的个数
// 测试链接 : https://leetcode.cn/problems/numbers-at-most-n-given-digit-set/
public class Code02_NumbersAtMostGivenDigitSet {
  public static int atMostNGivenDigitSet1(String[] strs, int num) {
    int tmp = num / 10;
    int len = 1;
    int offset = 1;
    while (tmp > 0) {
      tmp /= 10;
      len++;
      offset *= 10;
    }
    int m = strs.length;
    int[] digits = new int[m];
    for (int i = 0; i < m; i++) {
      digits[i] = Integer.valueOf(strs[i]);
    }
    return f1(digits, num, offset, len, 0, 0);
  }
  // offset是辅助变量，完全由len决定，只是为了方便提取num中某一位数字，不是关键变量
  // 还剩下len位没有决定
  // 如果之前的位已经确定比num小，那么free == 1，表示接下的数字可以自由选择
  // 如果之前的位和num一样，那么free == 0，表示接下的数字不能大于num当前位的数字
  // 如果之前的位没有使用过数字，fix == 0
  // 如果之前的位已经使用过数字，fix == 1
  // 返回最终<=num的可能性有多少种
  public static int f1(int[] digits, int num, int offset, int len, int free, int fix) {
    if (len == 0) {
      return fix == 1 ? 1 : 0;
    }
    int ans = 0;
    // num在当前位的数字
    int cur = (num / offset) % 10;
    if (fix == 0) {
      // 之前从来没有选择过数字
      // 当前依然可以不要任何数字，累加后续的可能性
      ans += f1(digits, num, offset / 10, len - 1, 1, 0);
    }
    if (free == 0) {
      // 不能自由选择的情况
      for (int i : digits) {
        if (i < cur) {
          ans += f1(digits, num, offset / 10, len - 1, 1, 1);
        } else if (i == cur) {
          ans += f1(digits, num, offset / 10, len - 1, 0, 1);
        } else {
          // i > cur
          break;
        }
      }
    } else {
      // 可以自由选择的情况
      ans += digits.length * f1(digits, num, offset / 10, len - 1, 1, 1);
    }
    return ans;
  }
  public static int atMostNGivenDigitSet2(String[] strs, int num) {
    int m = strs.length;
    int[] digits = new int[m];
    for (int i = 0; i < m; i++) {
      digits[i] = Integer.valueOf(strs[i]);
    }
    int len = 1;
    int offset = 1;
    int tmp = num / 10;
    while (tmp > 0) {
      tmp /= 10;
      len++;
      offset *= 10;
    }
    // cnt[i] : 已知前缀比num小，剩下i位没有确定，请问前缀确定的情况下，一共有多少种数字排列
    // cnt[0] = 1，表示后续已经没有了，前缀的状况都已确定，那么就是1种
    // cnt[1] = m
    // cnt[2] = m * m
    // cnt[3] = m * m * m
    // ...
    int[] cnt = new int[len];
    cnt[0] = 1;
    int ans = 0;
    for (int i = m, k = 1; k < len; k++, i *= m) {
      cnt[k] = i;
      ans += i;
    }
    return ans + f2(digits, cnt, num, offset, len);
  }
  // offset是辅助变量，由len确定，方便提取num中某一位数字
  // 还剩下len位没有决定，之前的位和num一样
  // 返回最终<=num的可能性有多少种
  public static int f2(int[] digits, int[] cnt, int num, int offset, int len) {
    if (len == 0) {
      // num自己
      return 1;
    }
    // cur是num当前位的数字
    int cur = (num / offset) % 10;
    int ans = 0;
    for (int i : digits) {
      if (i < cur) {
        ans += cnt[len - 1];
      } else if (i == cur) {
        ans += f2(digits, cnt, num, offset / 10, len - 1);
      } else {
        break;
      }
    }
    return ans;
  }
}

package class084;
// 统计整数数目
// 给你两个数字字符串 num1 和 num2 ，以及两个整数max_sum和min_sum
// 如果一个整数 x 满足以下条件，我们称它是一个好整数
// num1 <= x <= num2
// min_sum <= digit_sum(x) <= max_sum
// 请你返回好整数的数目
// 答案可能很大请返回答案对10^9 + 7 取余后的结果
// 注意，digit_sum(x)表示x各位数字之和
// 测试链接 : https://leetcode.cn/problems/count-of-integers/
public class Code03_CountOfIntegers {
  public static int MOD = 1000000007;
  public static int MAXN = 23;
  public static int MAXM = 401;
  public static int[][][] dp = new int[MAXN][MAXM][2];
  public static void build() {
    for (int i = 0; i < len; i++) {
      for (int j = 0; j <= max; j++) {
        dp[i][j][0] = -1;
        dp[i][j][1] = -1;
      }
    }
  }
  public static char[] num;
  public static int min, max, len;
  public static int count(String num1, String num2, int min_sum, int max_sum) {
    min = min_sum;
    max = max_sum;
    num = num2.toCharArray();
    len = num2.length();
    build();
    int ans = f(0, 0, 0);
    num = num1.toCharArray();
    len = num1.length();
    build();
    ans = (ans - f(0, 0, 0) + MOD) % MOD;
    if (check()) {
      ans = (ans + 1) % MOD;
    }
    return ans;
  }
  // 注意：
  // 数字，char[] num
  // 数字长度，int len
  // 累加和最小要求，int min
  // 累加和最大要求，int max
  // 这四个变量都是全局静态变量，所以不用带参数，直接访问即可
  // 递归含义：
  // 从num的高位出发，当前来到i位上
  // 之前决定的数字累加和是sum
  // 之前的决定已经比num小，后续可以自由选择数字，那么free == 1
  // 之前的决定和num一样，后续不可以自由选择数字，那么free == 0
  // 返回有多少种可能性
  public static int f(int i, int sum, int free) {
    if (sum > max) {
      return 0;
    }
    if (sum + (len - i) * 9 < min) {
      return 0;
    }
    if (i == len) {
      return 1;
    }
    if (dp[i][sum][free] != -1) {
      return dp[i][sum][free];
    }
    // cur : num当前位的数字
    int cur = num[i] - '0';
    int ans = 0;
    if (free == 0) {
      // 还不能自由选择
      for (int pick = 0; pick < cur; pick++) {
        ans = (ans + f(i + 1, sum + pick, 1)) % MOD;
      }
      ans = (ans + f(i + 1, sum + cur, 0)) % MOD;
    } else {
      // 可以自由选择
      for (int pick = 0; pick <= 9; pick++) {
        ans = (ans + f(i + 1, sum + pick, 1)) % MOD;
      }
    }
    dp[i][sum][free] = ans;
    return ans;
  }
  public static boolean check() {
    int sum = 0;
    for (char cha : num) {
      sum += cha - '0';
    }
    return sum >= min && sum <= max;
  }
}

package class084;
// 完全没有重复的数字个数
// 给定正整数n，返回在[1, n]范围内每一位都互不相同的正整数个数
// 测试链接 : https://leetcode.cn/problems/count-special-integers/
public class Code04_CountSpecialIntegers {
  public static int countSpecialNumbers(int n) {
    int len = 1;
    int offset = 1;
    int tmp = n / 10;
    while (tmp > 0) {
      len++;
      offset *= 10;
      tmp /= 10;
    }
    // cnt[i] :
    // 一共长度为len，还剩i位没有确定，确定的前缀为len-i位，且确定的前缀不为空
    // 0~9一共10个数字，没有选择的数字剩下10-(len-i)个
    // 那么在后续的i位上，有多少种排列
    // 比如：len = 4
    // cnt[4]不计算
    // cnt[3] = 9 * 8 * 7
    // cnt[2] = 8 * 7
    // cnt[1] = 7
    // cnt[0] = 1，表示前缀已确定，后续也没有了，那么就是1种排列，就是前缀的状况
    // 再比如：len = 6
    // cnt[6]不计算
    // cnt[5] = 9 * 8 * 7 * 6 * 5
    // cnt[4] = 8 * 7 * 6 * 5
    // cnt[3] = 7 * 6 * 5
    // cnt[2] = 6 * 5
    // cnt[1] = 5
    // cnt[0] = 1，表示前缀已确定，后续也没有了，那么就是1种排列，就是前缀的状况
    // 下面for循环就是求解cnt的代码
    int[] cnt = new int[len];
    cnt[0] = 1;
    for (int i = 1, k = 10 - len + 1; i < len; i++, k++) {
      cnt[i] = cnt[i - 1] * k;
    }
    int ans = 0;
    if (len >= 2) {
      // 如果n的位数是len位，先计算位数少于len的数中，每一位都互不相同的正整数个数，并累加
      // 所有1位数中，每一位都互不相同的正整数个数 = 9
      // 所有2位数中，每一位都互不相同的正整数个数 = 9 * 9
      // 所有3位数中，每一位都互不相同的正整数个数 = 9 * 9 * 8
      // 所有4位数中，每一位都互不相同的正整数个数 = 9 * 9 * 8 * 7
      // ...比len少的位数都累加...
      ans = 9;
      for (int i = 2, a = 9, b = 9; i < len; i++, b--) {
        a *= b;
        ans += a;
      }
    }
    // 如果n的位数是len位，已经计算了位数少于len个的情况
    // 下面计算一定有len位的数字中，<=n且每一位都互不相同的正整数个数
    int first = n / offset;
    // 小于num最高位数字的情况
    ans += (first - 1) * cnt[len - 1];
    // 后续累加上，等于num最高位数字的情况
    ans += f(cnt, n, len - 1, offset / 10, 1 << first);
    return ans;
  }
  // 之前已经确定了和num一样的前缀，且确定的部分一定不为空
  // 还有len位没有确定
  // 哪些数字已经选了，哪些数字没有选，用status表示
  // 返回<=num且每一位数字都不一样的正整数有多少个
  public static int f(int[] cnt, int num, int len, int offset, int status) {
    if (len == 0) {
      // num自己
      return 1;
    }
    int ans = 0;
    // first是num当前位的数字
    int first = (num / offset) % 10;
    for (int cur = 0; cur < first; cur++) {
      if ((status & (1 << cur)) == 0) {
        ans += cnt[len - 1];
      }
    }
    if ((status & (1 << first)) == 0) {
      ans += f(cnt, num, len - 1, offset / 10, status | (1 << first));
    }
    return ans;
  }
}

package class084;
// 至少有1位重复的数字个数
// 给定正整数n，返回在[1, n]范围内至少有1位重复数字的正整数个数
// 测试链接 : https://leetcode.cn/problems/numbers-with-repeated-digits/
public class Code04_NumbersWithRepeatedDigits {
  public static int numDupDigitsAtMostN(int n) {
    return n - countSpecialNumbers(n);
  }
  public static int countSpecialNumbers(int n) {
    int len = 1;
    int offset = 1;
    int tmp = n / 10;
    while (tmp > 0) {
      len++;
      offset *= 10;
      tmp /= 10;
    }
    int[] cnt = new int[len];
    cnt[0] = 1;
    for (int i = 1, k = 10 - len + 1; i < len; i++, k++) {
      cnt[i] = cnt[i - 1] * k;
    }
    int ans = 0;
    if (len >= 2) {
      ans = 9;
      for (int i = 2, a = 9, b = 9; i < len; i++, b--) {
        a *= b;
        ans += a;
      }
    }
    int first = n / offset;
    ans += (first - 1) * cnt[len - 1];
    ans += f(cnt, n, len - 1, offset / 10, 1 << first);
    return ans;
  }
  public static int f(int[] cnt, int num, int len, int offset, int status) {
    if (len == 0) {
      return 1;
    }
    int ans = 0;
    int first = (num / offset) % 10;
    for (int cur = 0; cur < first; cur++) {
      if ((status & (1 << cur)) == 0) {
        ans += cnt[len - 1];
      }
    }
    if ((status & (1 << first)) == 0) {
      ans += f(cnt, num, len - 1, offset / 10, status | (1 << first));
    }
    return ans;
  }
}