題目：求出1~13的整數中1出現的次數,并算出100~1300的整數中1出現的次數？為此他特别數了一下1~13中包含1的數字有1、10、11、12、13是以共出現6次,但是對于後面問題他就沒轍了。ACMer希望你們幫幫他,并把問題更加普遍化,可以很快的求出任意非負整數區間中1出現的次數。
參考：點選打開連結
分析：
考慮将n的十進制的每一位單獨拿出讨論，每一位的值記為weight。
1) 個位
從1到n，每增加1，weight就會加1，當weight加到9時，再加1又會回到0重新開始。那麼weight從0-9的這種周期會出現多少次呢？這取決于n的高位是多少，看圖：
以534為例，在從1增長到n的過程中，534的個位從0-9變化了53次，記為round。每一輪變化中，1在個位出現一次，是以一共出現了53次。
再來看weight的值。weight為4，大于0，說明第54輪變化是從0-4，1又出現了1次。我們記1出現的次數為count，是以：
count = round+1 = 53 + 1 = 54
如果此時weight為0（n=530），說明第54輪到0就停止了，那麼：
count = round = 53
2) 十位
對于10位來說，其0-9周期的出現次數與個位的統計方式是相同的，見圖：
不同點在于：從1到n，每增加10，十位的weight才會增加1，是以，一輪0-9周期内，1會出現10次。即rount*10。
再來看weight的值。當此時weight為3，大于1，說明第6輪出現了10次1，則：
count = round*10+10 = 5*10+10 = 60
如果此時weight的值等于0（n=504），說明第6輪到0就停止了，是以：
count = round*10+10 = 5*10 = 50
如果此時weight的值等于1（n=514） ，那麼第6輪中1出現了多少次呢？很明顯，這與 個位數的值有關，個位數為k，第6輪中1就出現了k+1次(0-k)。 我們記個位數為former，則：
count = round*10+former +1= 5*10+4 = 55
3) 更高位
更高位的計算方式其實與十位是一緻的，不再闡述。
4) 總結
将n的各個位分為兩類：個位與其它位。
對個位來說：
- 若個位大于0，1出現的次數為
round*1+1
- 若個位等于0，1出現的次數為
round*1
對其它位來說，記每一位的權值為base，位值為weight，該位之前的數是former，舉例如圖：
則：
- 若weight為0，則1出現次數為
round*base
- 若weight為1，則1出現次數為
round*base+former+1
- 若weight大于1，則1出現次數為
rount*base+base
當某一位的數字小于k時，那麼該位出現i的次數為：更高位數字x目前位數
當某一位的數字等于k時，那麼該位出現i的次數為：更高位數字x目前位數+低位數字+1
當某一位的數字大于k時，那麼該位出現i的次數為：(更高位數字+1)x目前位數
代碼：
package Solution19;
// 求出1~13的整數中1出現的次數,并算出100~1300的整數中1出現的次數？
// 為此他特别數了一下1~13中包含1的數字有1、10、11、12、13是以共出現6次,但是對于後面問題他就沒轍了。
// ACMer希望你們幫幫他,并把問題更加普遍化,可以很快的求出任意非負整數區間中1出現的次數。
public class Solution {
public int NumberOf1Between1AndN_Solution(int n) {
if (n < 1)
return 0;
int count = 0;
int base = 1;
int round = n;
while (round > 0) {
int weight = round % 10; //round的最後一位數,從個位數開始
round /= 10;
count += round * base;
if (weight == 1)
count += (n % base) + 1;
else if (weight > 1)
count += base;
base *= 10;
}
return count;
}
}
6. 時間複雜度分析
由分析思路或者代碼都可以看出，while循環的次數就是n的位數,logn（以10為底），而循環體内執行的操作都是有限次的，是以時間複雜度為O(logn)。
變型：計算數字k在0到n中的出現的次數，k可能是0~9的一個值
分析：此情形需要特殊考慮k=0的情況，其餘情況與上述k=1情況類似。
//計算數字k在0到n中的出現的次數，k可能是0~9的一個值
public int digitCounts(int k, int n) {
// write your code here
if(n<1 || k<0) return 0;
if(k==0 && n<10) return 1; //考慮特殊情況
int count=0;
int base=1;
int round=n;
while(round>0){
int weight=round %10; //round的最後一位，從個位開始
round/=10;
count+=round*base; //更高位數字*目前位數
if(weight==k){
count+=(n%base)+1;
}else if(weight<k){
count+=0;
}else{
if(!(k==0 && round==0)){ //排除沒有更高位時，尋找的數為0的情況 這種情況如n=19，k=0的情況，0為最高位時不應再加10
count+=base;
}
}
base*=10;
}
return count;
}