求 0~n 當中有幾個數字

$k(0\le k\le 9)$

想法 :

若

$k=0$ ，則要分開討論

1.

$k=0$

我們逐位討論，每一次將數字分為

$cur,$

$high,$

$low$ ，分別是現在這一位數，在他左邊的數，以及在他右邊的數。

以

$1034$ 為例：

$$ 第一次進入迴圈時

$high=103,$

$cur=4,$

$low=0,$

$base=1$。

$$ 因為

$cur\ne 0$ ，因此會有

$10,20,30...1030$ ，共

$103$ 個

$0$。

$$ 第二次進入迴圈時

$high=10,$

$cur=3,$

$low=4,$

$base=10$。

$$ 同樣因

$cur\ne 0$ ，因此會有

$100,101,102...300...1000$ ，共

$100$ 個

$0$。

$$ 第三次進入迴圈時

$high=1,$

$cur=0,$

$low=34,$

$base=100$。

$$ 這次

$cur=0$ ，因此會有

$1000,1001,1002...1034$ ，共

$35$ 個

$0$

最後不要忘記還有

$0$ 本身也是一個。

2.

$k>0$

同樣逐位討論，每一次將數字分為

$cur,$

$high,$

$low$ ，分別是現在這一位數，在他左邊的數，以及在他右邊的數。

以

$n=1034,k=2$ 為例：

$$ 第一次進入迴圈時

$high=103,$

$cur=4,$

$low=0,$

$base=1$。

$$ 因為

$cur>k$ ，因此會有

$2,12,22,32...1032$ ，共

$104$ 個

$2$。

$$ 第二次進入迴圈時

$high=10,$

$cur=3,$

$low=4,$

$base=10$。

$$ 同樣因

$cur>k$ ，因此會有

$20,21,22,23...320...1020$ ，共

$110$ 個

$2$。

$$ 第三次進入迴圈時

$high=1,$

$cur=0,$

$low=34,$

$base=100$。

$$ 這次

$cur<k$ ，因此會有

$200,201,202...299$ ，共

$100$ 個

$2$

實作 :

// just for 0
ll countDigit(ll n){
    if(n<1) return 1;
    ll high=n,tp=0,cur=0,low=0,base=1,ret=0;
    while(high>0){
        high=n/(10*base);
        tp=n%(10*base);
        cur=tp/base;
        low=tp%base;
        if(cur==0){
            ret+=(high-1)*base+low+1;
        }else{
            ret+=high*base;
        }
        base*=10;
    }
    return ret+1;
}

// only for 1~9
ll countDigit(ll n,ll k){
    if(k==0) return countDigit(n);
    ll high=n,tp=0,cur=0,low=0,base=1,ret=0;
    while(high>0){
        high=n/(10*base);
        tp=n%(10*base);
        cur=tp/base;
        low=tp%base;
        if(cur==k){
            ret+=high*base+low+1;
        }else if(cur<k){
            ret+=high*base;
        }else{
            ret+=(high+1)*base;
        }
        base*=10;
    }
    return ret;
}

tags: 程式設計