Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10n.
給出一個非負整數(shù)n，在 0 <= x <10 ^n 的范圍內，統(tǒng)計每一位都不重復的數(shù)字的個數(shù)
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])
想到的第一種方法是回溯，在個位數(shù)遍歷1 - 9，在其他位數(shù)上遍歷0-9（當然要注意已使用過的數(shù)字不能再使用），終止條件為當前的數(shù)字大于最大的數(shù)字（10 ^ n）
class Solution(object): def countNumbersWithUniqueDigits(self, n): """ :type n: int :rtype: int """ count = 1 # 因為個位數(shù)不能有0，所以個位數(shù)的循環(huán)放到回溯外面，分別統(tǒng)計一次個位數(shù)為 1 - 9 的元素不重復數(shù)字個數(shù) 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 # 只要小于最大數(shù)字，都保存統(tǒng)計，否則返回 if current_num < max_num: count += 1 else: return count # 遍歷 0 - 9 數(shù)字 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
第二種方法是動態(tài)規(guī)劃。
| 位數(shù) | 不重復元素個數(shù) | 總數(shù) |
|---|---|---|
| 1 | 10 | 10 |
| 2 | 9 * 9 | 91 |
| 3 | 9 * 9 * 8 | 739 |
| 4 | 9 * 9 * 8 * 7 | 986410 |
考慮以上規(guī)律，我們只需保存兩個變量，一個是上一個位數(shù)的不重復元素個數(shù)dp，另一個是可選數(shù)字個數(shù)selectable，這樣我們就可以得到遞推式 dp = dp * selectable，同時我們額外在維護一個總數(shù)就可以了
class Solution(object): def countNumbersWithUniqueDigits(self, n): """ :type n: int :rtype: int """ if n == 0: return 1 selectable = 9 # 當前可選項個數(shù) dp = 9 # 保存當前位數(shù)的元素不重復數(shù)字個數(shù)（不包括個位數(shù)） res = 10 # 元素不重復數(shù)字的總個數(shù) # 個位數(shù)的情況已經統(tǒng)計完成了，所以只需要統(tǒng)計n - 1次 for _ in range(n - 1): if selectable > 0: dp = dp * selectable res += dp selectable -= 1 return res新聞熱點
疑難解答
