题解【整数中1出现的次数（从1到n整数中1出现的次数）】

用数学思维来做。输入为N位数，则包含了输入最大的N-1位数（999..9）的解答
而1到9，1到99,1到999………………1到99999999这类输入的解是非常有规律性的。
分别为1，20,300,4000,50000；大大降低计算速度和空间。
例如输入为3426，则输出f（3426）为f（999）+1000到1999的1+2000到2999的1+3000到3426的1
而1000到1999中的1，和X000到X999中的1相比，多了1000个。X000到X999（x非1）等于f（999）
那么求f(3426)就变成求f(426)

int NumberOf1Between1AndN_Solution(int n)
{
if ( n == 0 )
return 0;
int x, c, h, i, s = 1,sum = 0;
h = n;
c = 1;
while( h >= 10 )
{
h /= 10; //最高位数字
c ++; //位数
}
if ( c == 1 )
return 1;
for (i=1;i<c-1;i++)
s *= 10;
x = n - h * pow( 10.0, c-1 ); //x是n去掉最高位剩下的数字
sum = h * ( c - 1 ) * s + NumberOf1Between1AndN_Solution( x );

if ( h > 1 )
        sum += pow( 10.0, c-1 );
else
    sum = sum + x +1;
return sum;   
}

}