力扣1012数位DP解法详解

问题本质计算[1, N]范围内至少有一位重复数字的正整数个数。直接计算较难可转化为计算没有重复数字的数的个数即各位数字互不相同的数然后用总数N减去该值 。核心思路计算[1, N]范围内数位互不相同的数的个数。数位 DP 状态设计dp[pos][mask][isLimit][isNum]pos: 当前处理到数字的第几位从高位到低位。mask: 一个位掩码10位记录0~9哪些数字已被使用过。isLimit: 当前位是否受到N对应位的限制即之前所有位都与N相同。isNum: 当前是否已经开始构造数字避免前导零被误判为使用数字0。记忆化搜索从最高位开始递归填充每一位在!isLimit isNum时缓存结果。最终答案N - countUnique(N)。C 代码实现class Solution { public: int numDupDigitsAtMostN(int n) { string s to_string(n); int m s.length(); // dp[pos][mask] 记忆化isLimitfalse 且 isNumtrue 时才缓存 vectorvectorint memo(m, vectorint(1 10, -1)); // 返回从 pos 开始构造已使用数字掩码为 mask能构造出的无重复数字的数的个数 // isLimit: 当前位是否受 n 的限制 // isNum:是否已经开始构造数字即是否跳过了前导零 functionint(int, int, bool, bool) dfs [](int pos, int mask, bool isLimit, bool isNum) - int { if (pos m) { // 构造完成如果已经开始构造数字isNumtrue则算一个有效数字 return isNum ? 1 : 0; } // 记忆化只有在不受限制且已经开始构造数字时结果才是可复用的 if (!isLimit isNum memo[pos][mask] ! -1) { return memo[pos][mask]; } int res 0; // 如果之前还没有开始构造数字这一位可以选择继续跳过即仍然不构造数字 if (!isNum) { // 跳过当前位即这一位不填数字mask 不变isLimitfalse因为跳过了相当于填了0但0不计入数字所以不受原数限制 res dfs(pos 1, mask, false, false); } // 确定当前位可以填的数字范围 int low isNum ? 0 : 1; // 如果还没开始构造不能填0避免前导零 int high isLimit ? s[pos] - 0 : 9; // 枚举当前位可以填的数字 for (int d low; d high; d) { // 检查数字 d 是否已经被使用过 if ((mask d) 1) continue; // 被使用过跳过 // 填入数字 d更新 mask更新 isLimit如果之前受限且当前位填的是上限值则后续仍受限 res dfs(pos 1, mask | (1 d), isLimit (d high), true); } // 缓存结果只有不受限制且已经开始构造数字的状态才缓存 if (!isLimit isNum) { memo[pos][mask] res; } return res; }; // 总共有 n 个数减去没有重复数字的数的个数即为至少有一位重复的数字的个数 return n - dfs(0, 0, true, false); } };复杂度分析时间复杂度O(m * 2^10 *10)其中m是N的位数最大为10。状态数为m * 2^10每个状态最多枚举 10 个数字。空间复杂度O(m * 2^10)用于记忆化存储。参考来源【leetcode】1012 至少有1位重复的数字排列组合LeetCode 3453.分割正方形 I二分查找203. Remove Linked List Elements143. Reorder List002. Add Two Numbers