?

Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10ⁿ.

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 10ⁿ.

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].

Credits:
Special thanks to @memoryless for adding this problem and creating all test cases.

?

這道題讓我們找一個范圍內的各位上不相同的數字，比如123就是各位不相同的數字，而11,121,222就不是這樣的數字。那么我們根據提示中的最后一條可以知道，一位數的滿足要求的數字是10個(0到9)，二位數的滿足題意的是81個，[10 - 99]這90個數字中去掉[11,22,33,44,55,66,77,88,99]這9個數字，還剩81個。通項公式為f(k) = 9 * 9 * 8 * ... (9 - k + 2)，那么我們就可以根據n的大小，把[1, n]區間位數通過通項公式算出來累加起來即可，參見代碼如下：

?

解法一：

class Solution { public:int countNumbersWithUniqueDigits(int n) {if (n == 0) return 1;int res = 0;for (int i = 1; i <= n; ++i) {res += count(i);}return res;}int count(int k) {if (k < 1) return 0;if (k == 1) return 10;int res = 1;for (int i = 9; i >= (11 - k); --i) {res *= i;}return res * 9;} };

?

下面這種方法是上面方法的精簡版，思路完全一樣：

?

解法二：

class Solution { public:int countNumbersWithUniqueDigits(int n) {if (n == 0) return 1;int res = 10, cnt = 9;for (int i = 2; i <= n; ++i) {cnt *= (11 - i);res += cnt;}return res;} };

?

最后我們來看題目提示中所說的回溯的方法，我們需要一個變量used，其二進制第i位為1表示數字i出現過，剛開始我們遍歷1到9，對于每個遍歷到的數字，現在used中標記已經出現過，然后在調用遞歸函數。在遞歸函數中，如果這個數字小于最大值，則結果res自增1，否則返回res。然后遍歷0到9，如果當前數字沒有在used中出現過，此時在used中標記，然后給當前數字乘以10加上i，再繼續調用遞歸函數，這樣我們可以遍歷到所有的情況，參見代碼如下：

?

解法三:

class Solution { public:int countNumbersWithUniqueDigits(int n) {int res = 1, max = pow(10, n), used = 0;for (int i = 1; i < 10; ++i) {used |= (1 << i);res += search(i, max, used);used &= ~(1 << i);}return res;}int search(int pre, int max, int used) {int res = 0;if (pre < max) ++res;else return res;for (int i = 0; i < 10; ++i) {if (!(used & (1 << i))) {used |= (1 << i);int cur = 10 * pre + i;res += search(cur, max, used);used &= ~(1 << i);}}return res;} };

?

參考資料：

https://leetcode.com/discuss/107981/backtracking-solution

https://leetcode.com/discuss/108119/java-concise-dp-solution

?

LeetCode All in One 題目講解匯總(持續更新中...)

總結

以上是生活随笔為你收集整理的[LeetCode] Count Numbers with Unique Digits 计算各位不相同的数字个数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。