首页 > 代码库 > 求整数范围中1的个数

求整数范围中1的个数

一、解法

1 public int NumberOf1Between1AndN_Solution(int n) {
2             int ones = 0;
3             for (long m = 1; m <= n; m *= 10){
4                 long a = n/m, b = n%m;
5                 //对应位置>=2的时候              //对应位置为1的时候
6                 ones += (a+8)/10*m +((a%10 == 1)? (b+1):0);
7             }
8             return ones;
9 }

二、思路

1、我们每次分别求个位,十位,百位,千位等等对应的1的个数。

2、举个例子求1-315中1的个数

  2-1 首先当m=1时,a = 315,b = 0,这个时候我们求的是个位为1的个数。

        此时个位的位置为5,大于2,我们用(a+8)/10来求得个位为1的数目,

        此时计算(315+8)/10等于32,表示一共有32个个位为1的整数,分别为

       (1,11,21,31,41,51,61,71,81,91,

        101,111,121,131,141,151,161,171,181,191,

        201,211,221,231,241,251,261,271,281,291,

        301,311),

        然后计算当个位的位置如果为1的时候,315%10 = 5, 5==1 为false,

        因此此时为0,此时个位为1一共有32个。

       

   2-2 再计算十位为1的个数,此时m=10,n=315,a=31,b=5,

        (a+8)/10等于3,3*10,表示十位为1的个数有30个,分别是

       (10,11,12,13,14,15,16,17,18,19,

          110,111,112,113,114,115,116,117,118,119,

          210,211,212,213,214,215,216,217,218,219),

        然后再计算(a%10 == 1) 由于a=31,所以为true,此时代表的

        十位为1的个数需要再加上(b+1)个,即6个,即十位为1的个数有

        36个。

 

   2-3 再计算百位为1的个数,此时m=100,n=315,a=3,b=15,

         (a+8)/10等于1,1*100,表示百位为1的个数有100个,分别是

       (100...199),再计算(a%10 == 1)为false,因此百位为1的个数

       一共有100个

    2-4 将个位,10位,百位加在一起一共有32+36+100 = 168个。

求整数范围中1的个数