首页 > 代码库 > 1到n的整数中,1出现的次数

1到n的整数中,1出现的次数

参考链接:https://discuss.leetcode.com/topic/18054/4-lines-o-log-n-c-java-python

 

1到n的整数中,1出现的次数,如11中,1出现了两次,并不是求包含1的数的个数

找规律:

假设n为六位数 abcdef.

求个位(f所在位)为1的数的个数C1:

  将n分为两部分:

    P = n / 1 = abcdef

    Q = n % 1 = 0

    对P,如果f > 1,则f的前缀从0~abcde,共(abcde+1)个 

           如果f == 1,则f的前缀从0~abcde-1, ,共(abcde)个

           当前缀为abcde时,f为1,即以abcde为前缀的数,对于前缀,abcde,对应的数为:abcdef,C1共(abcde * 1 ) + (Q+1) 个,共(abcde+1)个

           如果f == 0,则f的前缀从0~abcde-1,共(abcde)个

求十位(e所在位)为1的数的个数C10:

  将n分为两部分:

    P = n / 10 = abcde

    Q = n % 10 = f

    对P,如果e > 1,则e的前缀从0~abcd,对于每一个前缀,a‘b‘c‘d‘,它对应着十个数:a‘b‘c‘d‘1f‘(f‘从0到9),C10共( abcd +1 ) * 10个 

           如果e == 1,则e的前缀从0~abcd-1,对于每一个前缀,a‘b‘c‘d‘,它对应着十个数:a‘b‘c‘d‘1f‘(f‘从0到9)

               当前缀为abcd时,e为1,即以abcde为前缀的数,对于前缀,abcde,对应的数为:abcdef‘(f‘从0到f),C10共(abcd  * 10 ) + (Q+1) 个

           如果e == 0,则e的前缀从0~abcd-1,对于每一个前缀,a‘b‘c‘d‘,它对应着十个数:a‘b‘c‘d‘1f‘(f‘从0到9)

                                    当前缀为abcd时,e为0,没有十位为1的数,C10共(abcd  * 10 )个

求百位(d所在位)为1的数的个数C100:

  将n分为两部分:

    P = n / 100 = abcd

    Q = n % 100 = ef

    对P,如果d > 1,则d的前缀从0~abc,对于每一个前缀,a‘b‘c‘,它对应着一百个数:a‘b‘c‘1e‘f‘(e‘f‘从00到99),C100共(abc+1) * 100个 

           如果d == 1,则d的前缀从0~abc-1,对于每一个前缀,a‘b‘c‘,它对应着一百个数:a‘b‘c‘1e‘f‘(e‘f‘从00到99)

               当前缀为abc时,d为1,即以abcd为前缀的数,对于前缀,abcd,对应的数为:abcde‘f‘(e‘f‘从00到ef),C10共(abc * 100 ) + (Q+1) 个

           如果d == 0,则d的前缀从0~abc-1,对于每一个前缀,a‘b‘c‘,它对应着一百个数:a‘b‘c‘1e‘f‘(e‘f‘从00到99)

                                    当前缀为abc时,d为0,没有百位为1的数,C100共(abc * 100 )个

。。。。。。

设P = abcd

当d==0时,( P + 8 )/ 10 = abc

当d==1时,( P + 8 )/ 10 = abc

当d>1时,( P + 8 )/ 10 = abc+1

 

代码如下:

void countOne( int n )
{
    int cnt = 0;
    for( int m = 1; m <= n; m *= 10 )
    {
        int a = n / m;
        int b = n % m;
        cnt += ( ( a + 8 ) / 10 ) * m;
        if( a % 10 == 1 )
        {
            cnt += ( b+1 );
        }
    }
    return cnt;
}

 

3出现的次数也采用同样的办法:

int countT( int n )
{
    int cnt = 0;
    for( int m = 1; m <= n; m *= 10 )
    {
        int a = n / m;
        int b = n % m;
        cnt += ( ( a + 6 ) / 10 ) * m;
        if( a %10 == 3 )
        {
            cnt += ( b+1 );
        }
    }
    return cnt;
}

 

1到n的整数中,1出现的次数