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

要计算X出现的次数（），需统计X在每一位出现的次数。

1到10出现1次X；1到100出现10次X；1到1000出现100次X。

综上可以得出：从 1 至10i，在它们的左数第二位（右数第i位）中，任意的 X 都出现了10i1次。

Eg：以n=21345,X=1

依次分析X在各位中出现的次数：

个位：因为21340中有2134个10，所以从1到21340，1出现了2134次；再看从21341到21345，因为1<5（这里X为1，肯定满足，当X为任意数时，应判断X<5是否成立），所以1在个位中出现的次数为2135次。

十位：因为21300中有213个100，所以从1到21300，1出现在十位的次数为213*10次，再看从21301到21345，因为4>1,所以十位出现的次数为（213+1）*10^(2-1)=2140.

同理，百位出现的次数为（21+1）*10^(3-1)=2200.

千位：因为20000中共有2个10000，所以从1到20000，1出现在千位的次数为2*1000次，再看从20001到21345，因为1==1，所以千位中肯定含有1，但不会是1000次，而是345+1=346次（因为有21000，所以要加1），所以1出现在千位的总次数为2*10^(4-1)+（345+1）=2346次。

万位：方法同上，出现的次数为（0+1）*10^(5-1)=10000.

所以：21345中1出现的次数为2135+2140+2200+2346+10000=18821次

X在第i位出现的次数的计算方法：

1、取第i位左边（高位）的数字，乘以10^(i-1),得到基本的sum

2、取第i位数字：

1）如果大于X，则结果sum+=10^(i-1).

2）如果等于X，则结果为

sum+=（第i位右边的（低位）的数字）+1

3）如果小于X，则结果就为sum

代码如下：

size_tNumberOf1Between1AndN_Solution(size_tn){charstr[12]={0};intlength=strlen(_itoa(n,str,10));//计算n的位数size_tcountSum=0;//为取第i位数字简便，所以以下采取str运算for(inti=length-1;i>=0;--i){//取第i位左面的数字inttmpLeft=0;for(intj=0;j<i;++j){tmpLeft=tmpLeft*10+str[j]-'0';}countSum+=tmpLeft*pow(10,length-i-1);intiVal=str[i]-'0';//第i位的数字//如果大于X，则结果countSum+=pow(10,i).if(iVal>1){countSum+=pow(10,length-i-1);}//如果等于X,则结果为countSum+=（第i位右边的（低位）的数字）+1elseif(iVal==1){inttmpRight=0;//计算低位数字for(intj=i+1;j<length;j++){tmpRight=tmpRight*10+str[j]-'0';}countSum+=tmpRight+1;}//如果小于X，则结果就为countSum}returncountSum;}