题目：求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数。
见到这道题的第一反应可能是我可以先计算1~n每个数中1出现的次数，然后把所有结果相加即可。此时，时间复杂度为O(n*log(n)).
接下来是一种时间复杂度为O(log(n))的解法（这里以一个具体的例子来进行说明）：n=2234
1.将2234分为1~234，235~2234两段；
2.计算235~2234数字中出现1的次数。首先，出现在最高位上出现的次数。这里最高位为千位，由于最高位大于1,从1000~1999中，1一共出现103次；若最高位等于1，则1在最高位出现的次数为除去最高数字之后剩下的数字加1。其次，计算除去最高位外剩余位上出现的1.这里可以再将区间进行划分：235~1234和1235~2234.每段上出现1的次数是相同的：除去最高位剩余3位，选择其中一位是1，其余两位可以在0~9这10个数字中任意选择，所以每段出现的次数为3*102。最后，综合上述两步，在235~2234数字中出现1的次数为103+2*3*102；
3.递归采用步骤1,2计算1~234中出现1的次数。
public class Num31_NumberOf1Between1AndN {
public int NumberOf1Between1AndN_Solution(int n) {
int res = 0,len=1,num=n;
while((num/10)!=0){
len++;
num = num/10;
}//求出是几位数
res = doSum(n,len);
return res;
}
public int doSum(int end,int len) {
//若为1~0或者长度为0，直接返回0
if(end == 0||len==0)return 0;
//只剩一位的情况
if(len == 1 && end ==0)return 0;
if(len == 1 && end > 0)return 1;
int high,rest;
int pow = (int)Math.pow(10, len-1);//10^(len-1)
int mul = end/pow;//最高位
//求最高位上1的个数
if(mul==1)
high = end-pow+1;
else high = pow;
rest = mul * (len-1)*(pow/10);//除最高位以外，剩余位出现1的个数
//和的前两项为（end%pow+1 ~ end）中1出现的次数
//和的最后一项(1 ~ end%pow)中1的出现的次数
return high + rest +doSum(end-mul*pow,len-1);
}
}