知道是数位dp但是写不出来，太久没做了，哎…
只能再练习几道数位dp了

统计各位数字都不同的数字个数【LC357】

Given an integer n, return the count of all numbers with unique digits, x, where 0 <= x < 10ⁿ.

排列组合

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;// 次高位可以选择的数字个数 然后依次减1for (int i = 2; i <= n; i++){int cur = last * choice;res += cur;last = cur;choice--;}return res;}
  }
  

  • 复杂度

    • 时间复杂度：O(n)O(n)O(n)
    • 空间复杂度：O(1)O(1)O(1)

数位dp

2022/11/28

• 题目升级：回答任意区间[l,r][l,r][l,r] 内合法数的个数。

• 思路：数位dp

  首先将 nnn 转换成字符串 sss，定义 f(i,mask,isLimit,isNum)f(i,mask,isLimit,isNum)f(i,mask,isLimit,isNum) 表示构造从左往右第 iii 位及其之后数位的合法方案数，即各位数字都不同的数字个数，其余参数的含义为：

  • iii表示当前构造至从左往右第iii位

  • maskmaskmask表示前面选过的数字集合，换句话说，第 iii 位要选的数字不能在 maskmaskmask中。

    • 用低十位表示数字 [0,9] 是否被使用**(int 变量）**

  • isLimitisLimitisLimit 表示当前是否受到了 nnn的约束。若为真，则第 iii 位填入的数字至多为 s[i]s[i]s[i]，否则可以枚举至 9。如果在受到约束的情况下填了 s[i]s[i]s[i]，那么后续填入的数字仍会受到 nnn的约束。

    • 取决于第i−1i-1i−1位填充是否受限，以及当前填充的数是否达到上限值

  • isNumisNumisNum 表示 iii前面的数位是否填了数字。若为假，则当前位可以跳过（不填数字），或者要填入的数字至少为 111；若为真，则要填入的数字可以从 000开始。

    • 在本题中，不允许前导0的存在，因此本题需要参数isNum

  那么 f(0,0,true,false)f(0,0,true,false)f(0,0,true,false) 即为最终结果

• 实现

  • 首先位数nnn对应的数值最大值为10n−110^n-110n−1，将其存入字符数组s，存储高位至低位的数值大小，会影响isLimit【本题需要判断的数值范围为**[0,10^n-1]**】

  • 然后使用dpdpdp数组记录在不受到约束时，第iii位枚举范围固定时的合法方案数，即从左往右第iii位之后所有数位不相同的数字个数【不包括第iii位】

  • 如果不受限并且前一位是数值，那么可以查询是否已经计算过第iii位枚举范围一定时的合法方案数，若dp[i][mask] >= 0，则表示已经计算过，可直接返回

    • 比如当n=4时，枚举范围为0-9999，12XX和21XX的合法方案数相同，可直接查询得到

  • 否则枚举第iii位的可能性【既可以填入数字，也可以不填入数字】

    • 不填入数字：如果isNum为false，那么第iii位也可以不填入数字

      此时对结果的贡献为f(i+1,mask,false,false)

    • 填入数字：通过for循环，枚举每一位其所有可能的值d

      1. 初始值：可能为0或者1
         • isNum为true即前一位为数字时，那么第iii位可以从0开始枚举
         • 否则，只有最低位可以从0开始枚举，其他位均从1开始枚举【LC1012 最低位也从1开始枚举】
      2. 上限值：由limit决定
         • 如果受限，那么枚举的最大值为s[i]
      3. 只有d不在mask中时，才对结果有贡献，共享为f(i+1,mask | d,isLimit && d==up,true)

  • 如果不受限并且前一位为数值，那么记录result至dp数组中

• 代码

  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);}//最小值为0int 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;}
  }
  

  • 复杂度

    • 时间复杂度：O(n)O(n)O(n)，nnn为数字的位数，时间复杂度 = 状态个数 * 单个状态的转移次数，状态个数就是 dp 数组的长度，即 O(n)O(n)O(n)，而单个状态的转移次数 = O(10) = O(1)，所以时间复杂度为 O(n)O(n)O(n)
    • 空间复杂度：O(n)O(n)O(n)

至少有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);}// 最小值为1int 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) // 枚举要填入的数字 dif ((mask >> d & 1) == 0) // d 不在 mask 中// mask | (1 << d) 将mask的第d位赋值为1res += 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）
  著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
  

  • 复杂度

    • 时间复杂度：O(logn)O(log n)O(logn)，n为数字的位数，时间复杂度 = 状态个数 * 单个状态的转移次数，状态个数就是 dp 数组的长度，即 O(logn)O(logn)O(logn)，而单个状态的转移次数 = O(10) = O(1)，所以时间复杂度为 O(logn)O(log n)O(logn)
    • 空间复杂度：O(logn)O(log n)O(logn)