题目一

给定n，和个位数k。计算从0-n的数中，包含k的次数。

方法一

暴力法，直接遍历每个数，处理每个数。

int counts1(int v,int k)
{
    int counts=0;
    int tmp;
    for(int i = 0 ;i<=v;i++)
    {
        tmp = i;
        while(tmp)
        {
            if(tmp%10 == k)
            {
                counts++;
                
            }
            tmp/=10;
        }
    }
    return counts;
}

方法二

数学的方法

寻找规律使用数学的方法，往往更加高效，但是更加不好理解。

找规律

从1到n，我们将其分段，也就是，一位数，两位数，三位数。。。。
然后分别计算这些段中含k的次数
假设abcdef
当我们在计算，百位d的时候，也就是三位数的时候。

1. 当d<k：百位重复多少次，那么百位k就出现多少次，二百位重复的次数，恰恰时abc000次。
2. 当d=k：同上adc000次，但是此时，从百位还自带abck00-abckef中的，xx次和k00这个数
   所以，这种情况k出现的次数位abc000+ef+1
3. 当d>k：同上abc000次，此时，还自带abck000-abc(k+1)000中的k
   所以出现k的情况位abc000+1000。

int counts2(int v,int k)
{
    v=v>=0?v:-v;
    if(k>9)
    {
        return -1;
    }

    int ten=1;
    int counts=0;

    int cur,low,high;
    
    while(v/ten != 0)
    {
        cur = (v/ten)%10;
        low = v%ten;
        high = v/(ten*10);
        cout<<"v:ten:high:cur:low = "<<v<<" : "<<ten<<" : "<<high<<" : "<<cur<<" : "<<low<<endl;

        if(cur<k)
        {
            counts+=high*ten;
        }else if(cur == k){
            counts+=high*ten+low+1;
        }else if(cur > k){
            counts+=(high+1)*ten;
        }

        ten*=10;
    }

    return counts;
}

数学的方法虽然计算速度快。但是都比较难理解，而且，扩展性都奇差无比！！

题目二

编程之美中还有题目二，但是这个题目二算是纯数学的了，太恐怖。