Leetcode題解 CountNumberswithUniqueDigits

點擊上方“程序員大白”，選擇“星標”公眾號

題意

題目：對唯一數(shù)字組成的數(shù)進行計數(shù)  給定一個非負整數(shù)n，對唯一數(shù)字組成的數(shù)x進行計數(shù)，其中0 <= x <= 10 ^ n.  舉個例子：  給定 n = 2，應當返回 91.  

題解

算法及復雜度（0 ms）  根據(jù)排列組合的知識，要想得到每個數(shù)字都不重復的數(shù)，對于一個n位數(shù)（1 <= n <= 10），第一個位置有9中可能，第二個位置有9中可能，第三個位置8中，...  由于本題，所求的是0 <= x <= 10 ^ n范圍內所有的數(shù)，所以可以設dp[i]表示<= x <= 10 ^ i所有滿足條件的x的個數(shù)， 那么dp[i + 1] = 9 * 9 * 8...(共i個) + dp[i].  可以看到，本題存在遞推的關系，但是并不存在重疊子問題的性質，可以直接使用遞推的方法進行求解.  

時間復雜度: O(n).  

舉個例子

// 輸入數(shù)據(jù) n = 3

// 初始化
dp[0] = 1

// i = 1時
dp[1] = 9 + dp[0] = 10

// i = 2時
dp[2] = 9 * 9 + dp[1] = 91

// i = 3時
dp[3] = 9 * 9 * 8 + dp[2] = 739

// 返回結果
return 739

CPP代碼

class Solution {
public:
    int countNumbersWithUniqueDigits(int n) {
        
        vector<int> dp(11);
        dp[0] = 1;
        
        for(int i = 1; i <= 10; i ++) {
            int temp = 9;
            for(int j = 9; j > 10 - i; j--) {
                temp *= j;
            }
            dp[i] = temp + dp[i - 1];
        }
        
        if(n > 10) return dp[10];
        else return dp[n];
    }
};

重磅！程序員大白交流群-學術微信交流群已成立

額外贈送福利資源！邱錫鵬深度學習與神經網(wǎng)絡，pytorch官方中文教程，利用Python進行數(shù)據(jù)分析，機器學習學習筆記，pandas官方文檔中文版，effective java（中文版）等20項福利資源
獲取方式：進入群后點開群公告即可領取下載鏈接

注意：請大家添加時修改備注為 [學校/公司 + 姓名 + 方向]
例如 —— 哈工大+張三+對話系統(tǒng)。
號主，微商請自覺繞道。謝謝！

推薦閱讀
“拍一拍” 能撤回了 ！！！
5款Chrome插件，第1款絕對良心！
為開發(fā)色情游戲，這家公司赴日尋找AV女優(yōu)拍攝，期望暴力賺錢結果...
拼多多終于釀成慘劇
華為阿里下班時間曝光：所有的光鮮，都有加班的味道

關于程序員大白

程序員大白是一群哈工大，東北大學，西湖大學和上海交通大學的碩士博士運營維護的號，大家樂于分享高質量文章，喜歡總結知識，歡迎關注[程序員大白]，大家一起學習進步！