知道是数位dp但是写不出来，太久没做了，哎…
只能再练习几道数位dp了
统计各位数字都不同的数字个数【LC357】
Given an integer n, return the count of all numbers with unique digits, x, where 0 <= x < 10n.
排列组合
2022/11/27
思路：根据排列组合原理，由于要求各位数字都不相同，因此每位数字可以选择的范围是一定的，最高位可选择的数值个数为 9，而从次高位开始到最低位，可选的个数从 9 开始逐一递减
因此使用乘法原理，每位数可选的数值个数相乘即是长度为 n的数的可能方案数 cur，而所有长度 [1,n] 的方案数累加即是答案。
作者：宫水三叶
链接：https://leetcode.cn/problems/count-numbers-with-unique-digits/solutions/1411205/by-ac_oier-6tfl/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
实现
class Solution { public int countNumbersWithUniqueDigits(int n) { if (n == 0){ return 1; } int res = 10; int last = 9;// 最高位可以选择的数字个数 int choice = 9;// 次高位可以选择的数字个数 然后依次减1 for (int i = 2; i <= n; i++){ int cur = last * choice; res += cur; last = cur; choice--; } return res; } }
数位dp
2022/11/28
class Solution { char[] s; int[][] dp; public int countNumbersWithUniqueDigits(int n) { int num = (int)(Math.pow(10,n) - 1); s = Integer.toString(num).toCharArray(); int len = s.length; dp = new int[len][1 << 10]; for (int i = 0; i < len;i++){ Arrays.fill(dp[i],-1); } return f(0, 0, true, false); } //最小值为0 int f(int i, int mask, boolean isLimit, boolean isNum) { if (i == s.length) { return isNum ? 1 : 0; } if (!isLimit && isNum && dp[i][mask] >= 0){ return dp[i][mask]; } int res = 0; // isNum为false 可不填 if (!isNum){ res += f(i + 1, mask, false, false); } int up = isLimit ? s[i] - '0' : 9; for (int d = isNum || i == s.length - 1 ? 0 : 1;d <= up; d++){ if ( (mask >> d & 1) == 0){ res += f(i + 1, mask | (1 << d),isLimit && d == up, true); } } if (!isLimit && isNum){ dp[i][mask] = res; } return res; } }
至少有1位重复的数字【LC1012】
Given an integer
n, return the number of positive integers in the range[1, n]that have at least one repeated digit.
2022/11/28
- 思路：将题目转化为[1,n]范围内所有数的个数减去各位数字都不同的数字个数，因此可采用同统计各位数字都不同的数字个数【LC357】相同的数位dp思路，只需将最低位的枚举数值改为从1开始即可
- 代码
class Solution { char s[]; int dp[][]; public int numDupDigitsAtMostN(int n) { s = Integer.toString(n).toCharArray(); var m = s.length; dp = new int[m][1 << 10]; for (var i = 0; i < m; i++) Arrays.fill(dp[i], -1); return n - f(0, 0, true, false); } // 最小值为1 int f(int i, int mask, boolean isLimit, boolean isNum) { if (i == s.length) return isNum ? 1 : 0;// 前一位为数字才有合法数字 if (!isLimit && isNum && dp[i][mask] >= 0) return dp[i][mask]; var res = 0; if (!isNum) res = f(i + 1, mask, false, false); // 前一位不是数字 那么可以跳过当前数位 // 前一位为数字，那么第i位可以从0开始枚举；否则，均从1开始枚举【与LC357的区别，合法数的范围为[1,n]】 for (int d = isNum ? 0 : 1, up = isLimit ? s[i] - '0' : 9; d <= up; ++d) // 枚举要填入的数字 d if ((mask >> d & 1) == 0) // d 不在 mask 中 // mask | (1 << d) 将mask的第d位赋值为1 res += f(i + 1, mask | (1 << d), isLimit && d == up, true); if (!isLimit && isNum) dp[i][mask] = res; return res; } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/numbers-with-repeated-digits/solutions/1748539/by-endlesscheng-c5vg/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
