题目：求出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的次数。
1 public class Num31_NumberOf1Between1AndN { 2 3 public int NumberOf1Between1AndN_Solution(int n) { 4 int res = 0,len=1,num=n; 5 while((num/10)!=0){ 6 len++; 7 num = num/10; 8 }//求出是几位数 9 res = doSum(n,len); 10 return res; 11 } 12 public int doSum(int end,int len) { 13 //若为1~0或者长度为0，直接返回0 14 if(end == 0||len==0)return 0; 15 //只剩一位的情况 16 if(len == 1 && end ==0)return 0; 17 if(len == 1 && end > 0)return 1; 18 19 int high,rest; 20 int pow = (int)Math.pow(10, len-1);//10^(len-1) 21 int mul = end/pow;//最高位 22 //求最高位上1的个数 23 if(mul==1) 24 high = end-pow+1; 25 else high = pow; 26 rest = mul * (len-1)*(pow/10);//除最高位以外，剩余位出现1的个数 27 //和的前两项为（end%pow+1 ~ end）中1出现的次数 28 //和的最后一项(1 ~ end%pow)中1的出现的次数 29 return high + rest +doSum(end-mul*pow,len-1); 30 } 31 }