题目：
求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数。
思路：
比如求1到34597中1出现的次数。首先划分两段：1到4597,4598到34597.
第二段的话，最高位1出现的次数为10000~19999，总共10000次（假设n的位数为b，即10的b次方个）；另一部分是其他位的1。
对于求其他位的1，将第二段再次划分：4598到14597,14598到24597,24598到34597.对于每一段，选定一位为1时，其余位置可以为0~9中任意一个，则每段有10X10X10X3个；总共有10X10X10X3X3个。即10的（b-2）次方乘以(b-2)乘以最高位数字。
这样，整个第二段4598到34597的个数求得，对于第一段用递归方法求即可。
总结，可以将1到n划分为这样几步：（假设n的位数为len，最高位数字为first，n也记为abxxx...）
A. 从1到bxxx... 递归求解
B.a 从bxxx...+1到abxxx...的最高位1个数：如果first>1，则为10的first次方；否则为bxxx...+1个。
B.b 从bxxx...+1到abxxx...的除最高位有1外，其他位1的个数：10的(len-2)次方乘以(len-1)乘以first个。
注意：
实现的时候，可以用字符串来处理数字n。这样去掉最高位后的数字，只需要将字符指针加1即可。
需要注意的输入：长度为1，且first为0；长度为1，且first>0。（因为后面有len-2）
代码：
class Solution {
public:
int NumberOf1Between1AndN_Solution(int n)
{
if(n<=) return ;
char s[];
sprintf(s,"%d",n);
return NumberOf1(s);
}
private:
int NumberOf1(char *s)
{
if(s==NULL || *s<'' || *s>'' || *s=='\0') return ;
int len=strlen(s);
int first=s[]-'';//最高位数字
if(len==1 && first==0) return 0;
if(len==1 && first>0) return 1;
int numFirstDigit=;//最高位的1的个数
if(first>) numFirstDigit=PowerOf10(len-);
else if(first==)
numFirstDigit=atoi(s+1)+;
int numOtherDigit=;//其他位的1的个数
if(len>=)
numOtherDigit=PowerOf10(len-)*first*(len-1);
int numRecursive=NumberOf1(s+);//递归求解的1的个数
return numFirstDigit+numOtherDigit+numRecursive;
}
int PowerOf10(int n)
{
int res=;
for(int i=;i<n;++i)
{
res=res*;
}
return res;
}
};
讨论：
在B.b的求个数过程中，是不是有重复的，比如选定第二位为1时，其他位可以从0到9任选，而选定第三位为1时，其他为又是从0到9任选。这样，对于形如”第二位为1、第三位为1“的数字，则重复计算了。
同样，B.b和B.a的计算中，好像也是有重复计算了的。
是我理解错了吗？求讨论。
答：我理解错了，并没有重复计数。