Problem

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

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

題意

給出一個(gè)非負(fù)整數(shù)n，計(jì)算所有滿足以下條件的x：

1. 0 ≤ x < 10^n
2. x中沒(méi)有重復(fù)數(shù)字（如121就不滿足,因?yàn)橛袃蓚€(gè)1）

分析

本題可以有兩種做法，一種是利用純數(shù)學(xué)方法，計(jì)算排列數(shù)即可；另一種是利用回溯的思想，有點(diǎn)類似于LeetCode# 526: Beautiful Arrangement，將不同的數(shù)字放置在不同的位置，求得滿足條件的放置方法數(shù)即可。

數(shù)學(xué)方法

題意可轉(zhuǎn)化為，在1個(gè)(n = 0, 1)或n個(gè)(n ≥ 2)位置上放置0-9這十個(gè)數(shù)字，是高中時(shí)候就學(xué)過(guò)的排列問(wèn)題。

1. 對(duì)于n=0的情況，滿足條件的數(shù)字只有0，只有1個(gè)；
2. 對(duì)于n=1的情況，滿足條件的數(shù)字有0, 1, ..., 9，有10個(gè)；
3. 對(duì)于n=2的情況，對(duì)于一位數(shù)，滿足條件的有10個(gè)；對(duì)于兩位數(shù)，問(wèn)題變成了，從0-9這十個(gè)數(shù)字中挑出兩個(gè)分別放置在十位和個(gè)位，是A(2, 10)；但是要注意0不能放在十位，所以要去掉A(1, 9)個(gè)數(shù)字，最后的結(jié)果：result[2] = A(2, 10) - A(1, 9) + result[1]
4. 對(duì)于n > 2的情況不再贅述。

回溯方法

//TODO

Code

數(shù)學(xué)方法

//Runtime: 0ms（精度不夠）
class Solution {
private:
    vector<int> fac;     //fac[i] = i!
    vector<int> result;  //result[i] = result of i
    void _calFac(){
        fac.resize(11);
        fac[0] = 1;
        for (int i = 1; i <= 10; i++)
            fac[i] = i * fac[i - 1];
        return;
    }
    void _calRst(int n){
        result.resize(n + 1);
        result[0] = 1;
        for (int i = 1; i <= n; i++)
            result[i] = fac[10] / fac[10 - i] - fac[9] / fac[10 - i] + result[i - 1];
        return;
    }
public:
    int countNumbersWithUniqueDigits(int n) {
        if (n > 10) return 0;
        _calFac();
        _calRst(n);
        return result[n];
    }
};

Backtracking

//TODO