《劍指offer》-整數中1出現的次數 - zjutzz－IT工程師數位筆記本

文章出處

題目描述
求出1~13的整數中1出現的次數,并算出100~1300的整數中1出現的次數？為此他特別數了一下1~13中包含1的數字有1、10、11、12、13因此共出現6次,但是對于后面問題他就沒轍了。ACMer希望你們幫幫他,并把問題更加普遍化,可以很快的求出任意非負整數區間中1出現的次數。

直接暴力可以過。但是不優美。
嘗試推導公式，思路是遞歸求解，發現假如n都是999，99999這種全9的數字會很好處理：f(n)=g(t)*f(h(n)), 其中t表示n的第一個位，h(n)表示n去掉第一位，g(t)要特別考慮1的情況。

但是n很可能連一個9都沒有。沒關系，那就把n切分成兩部分，一部分是能用99999這種處理的，另一部分是再單獨計算的。

而其實這兩個部分是可以合并的，99999的情況是后者的特例而已。

利用數字特點和規律，計算每一位上1出現的次數：
例如百位上1出現次數，數值n在百位上的值是curNum則：

if(curNum==0)
1出現的次數等于比百位更高位數100。例如n=1023，高位數就是1，百位上出現1的次數是1100；

if(curNum==1)
1出現的次數等于比百位更高位數100，再加上低位上的數，再加1。例如n=1123，高位數就是1，低位數是23，百位上出現1的次數是1100+23+1；

if(curNum>1)
1出現的次數等于比百位更（高位數+1）100,例如n=1223，高位數就是1，次數百位上出現1的次數是（1+1）100；

而其實這種策略是適用于各個位的，不僅僅是在百位上。那么直接上碼吧：

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n)
    {
        int count=0;
        int factor=1;
        while(n/factor!=0){
            int curNum = (n/factor)%10;
            int lowNum = n%factor;
            int highNum = n/(factor*10);
            
            if(curNum==0){
                count += factor*highNum;
            }
            else if(curNum==1){
                count += factor*highNum + lowNum + 1;
            }
            else{
                count += factor*(highNum + 1);
            }
            factor *= 10;
        }
        return count;
    }
};