357. Count Numbers with Unique Digits

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

給定一個非負(fù)整數(shù)n，統(tǒng)計[0，10ⁿ）之間僅含不同數(shù)字的數(shù)。

分析：

　　給定n，求[0，10ⁿ）范圍內(nèi)各位均不相同的數(shù)的個數(shù)，可分別求出[0，10¹），[10¹，10²），……，[10^n-1，10ⁿ）各區(qū)間內(nèi)符合條件的數(shù)的個數(shù)，再相加即為所求。

　　求第k個區(qū)間[10^k-1，10^k）內(nèi)包含不同數(shù)字的數(shù)，即求所有k位數(shù)中符合條件的數(shù)。可通過排列組合來求得。第1位可取1~9共9種；第2位可取0~9，除去第1位所取的數(shù)字，共9種；第3位可取0~9，除去第1、第2位所取數(shù)字，共8種，……，第k位可取0~9，除去第1~k-1位所取數(shù)字，共（10-（k-1））=11-k種，記為f(k)，即f(k)=11-k。

　　所以所求結(jié)果即為f(1)+f(2)+...+f(k)。

　　注意：1）當(dāng)n=0時，取值范圍為[0，1），0符合條件，即f(0)=1。2）n>10時，11位以上的數(shù)必含有相同數(shù)字，因此，f(k)=0（k>10）。

代碼如下：

int countNumbersWithUniqueDigits(int n) {if (n <= 0) return 1;if (n == 1) return 10;int rst = 10, cnt = 2, coef = 9;int maxCnt = n > 10 ? 10 : n;while (cnt <= maxCnt){coef *= (11 - cnt);rst += coef;cnt++;}return rst; }

　　

posted on 2018-03-20 15:44 bigpotato 閱讀(...) 評論(...) 編輯 收藏

轉(zhuǎn)載于:https://www.cnblogs.com/big-potato/p/8609686.html

總結(jié)

以上是生活随笔為你收集整理的357. Count Numbers with Unique Digits的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。