題目鏈接：https://leetcode.com/problems/count-numbers-with-unique-digits/
題目：
Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10n.
Example:
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])
Hint:
A direct way is to use the backtracking approach.
Backtracking should contains three states which are (the current number, number of steps to get that number and a bitmask which represent which number is marked as visited so far in the current number). Start with state (0,0,0) and count all valid number till we reach number of steps equals to 10n.
This problem can also be solved using a dynamic programming approach and some knowledge of combinatorics.
Let f(k) = count of numbers with unique digits with length equals k.
f(1) = 10, …, f(k) = 9 * 9 * 8 * … (9 - k + 2) [The first factor is 9 because a number cannot start with 0].
思路：
遞推方程都給了，傻子采取回溯。。= =。。而且回溯看起來(lái)好難的模樣。。
算法：
public int countNumbersWithUniqueDigits(int n) {
if (n == 0)
return 1;
int count = 0;
for (int i = 1; i <= n; i++) {// 求每位有多少unique digits
count += cal(i);
}
return count;
}
public int cal(int k) {
int sum = 9;
if (k == 0)
return 0;
if (k == 1)
return 10;
for (int i = 11 - k; i <= 9; i++) {
sum *= i;
}
return sum;
}
程序員人生，我編程，我富裕，記住wfuyu網(wǎng)，php教程，php學(xué)習(xí)，php手冊(cè)，CMS模版制作
聲明：本站大部分內(nèi)容是作者原創(chuàng)，少部分收集于互聯(lián)網(wǎng)供大家一起學(xué)習(xí)，原版權(quán)很多不明，如有侵權(quán)請(qǐng)聯(lián)系本站，謝謝！
粵ICP備14040726號(hào)-1?? 2015-2020 程序員人生 版權(quán)所有
