class084 数位dp-上【算法】
code1 357. 统计各位数字都不同的数字个数
// 统计各位数字都不同的数字个数
// 给你一个整数n，代表十进制数字最多有n位
// 如果某个数字，每一位都不同，那么这个数字叫做有效数字
// 返回有效数字的个数，不统计负数范围
// 测试链接 : https://leetcode.cn/problems/count-numbers-with-unique-digits/
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;
}
}code2 902. 最大为 N 的数字组合
// 最大为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/
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;
}
}code3 2719. 统计整数数目
// 统计整数数目
// 给你两个数字字符串 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/
[0,num2]-[0,num1-1]
=[0,num2]-[0,num1]+[num1]，因为字符串的减法不好做，所以单独判断num1，是否符合
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;
}
}code4 2376. 统计特殊整数
// 完全没有重复的数字个数
// 给定正整数n，返回在[1, n]范围内每一位都互不相同的正整数个数
// 测试链接 : https://leetcode.cn/problems/count-special-integers/
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;
}
}code4 1012. 至少有 1 位重复的数字
// 至少有1位重复的数字个数
// 给定正整数n，返回在[1, n]范围内至少有1位重复数字的正整数个数
// 测试链接 : https://leetcode.cn/problems/numbers-with-repeated-digits/
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;
}
}2023-12-15 15:12:01