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