Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10n.
给出一个非负整数n，在 0 <= x <10 ^n 的范围内，统计每一位都不重复的数字的个数
Given n = 2, return 91. (The answer should be the total numbers in the range of 0 ≤ x < 100, excluding [11,22,33,44,55,66,77,88,99])
想到的第一种方法是回溯，在个位数遍历1 - 9，在其他位数上遍历0-9（当然要注意已使用过的数字不能再使用），终止条件为当前的数字大于最大的数字（10 ^ n）
class Solution(object): def countNumbersWithUniqueDigits(self, n): """ :type n: int :rtype: int """ count = 1 # 因为个位数不能有0，所以个位数的循环放到回溯外面，分别统计一次个位数为 1 - 9 的元素不重复数字个数 for i in range(1, 10): selectable = list(range(10)) selectable.remove(i) count += self.solve(list(range(2, 10)), pow(10, n), i) return count def solve(self, selectable, max_num, current_num): count = 0 # 只要小于最大数字，都保存统计，否则返回 if current_num < max_num: count += 1 else: return count # 遍历 0 - 9 数字 for index_s, s in enumerate(selectable): count += self.solve(selectable[:index_s] + selectable[index_s + 1:], max_num, current_num * 10 + s) return count不过得到了 Time Limit Exceeded
第二种方法是动态规划。
| 位数 | 不重复元素个数 | 总数 |
|---|---|---|
| 1 | 10 | 10 |
| 2 | 9 * 9 | 91 |
| 3 | 9 * 9 * 8 | 739 |
| 4 | 9 * 9 * 8 * 7 | 986410 |
考虑以上规律，我们只需保存两个变量，一个是上一个位数的不重复元素个数dp，另一个是可选数字个数selectable，这样我们就可以得到递推式 dp = dp * selectable，同时我们额外在维护一个总数就可以了
class Solution(object): def countNumbersWithUniqueDigits(self, n): """ :type n: int :rtype: int """ if n == 0: return 1 selectable = 9 # 当前可选项个数 dp = 9 # 保存当前位数的元素不重复数字个数（不包括个位数） res = 10 # 元素不重复数字的总个数 # 个位数的情况已经统计完成了，所以只需要统计n - 1次 for _ in range(n - 1): if selectable > 0: dp = dp * selectable res += dp selectable -= 1 return res新闻热点
疑难解答
