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新聞熱點
疑難解答
