当前位置: 代码迷 >> Java相关 >> 微软算法100题30 在从1到n的整数中一出现的次数
  详细解决方案

微软算法100题30 在从1到n的整数中一出现的次数

热度:21   发布时间:2016-04-22 19:32:46.0
微软算法100题30 在从1到n的整数中1出现的次数

30. 在从1到n的整数中1出现的次数
题目:输入一个整数n,求从1到n 这n个整数的十进制表示中1出现的次数。
例如输入12,从1到12这些整数中包含1的数字有1,10,11 和12,1 一共出现了5 次。
分析:这是一道广为流传的google 面试题

 

思路:

第一反应是遍历这N个数,然后对每个正数n不断用10取余来求各个位上1的次数,同理对每个数求1出现的次数并累加,但这种方法的时间复杂度是o(n),当n值很高时耗时太久

第二个思路是能不能通过数学的方法找到n上所有1的次数 (自己实在是想不出来,先从网上搜了一下,最后发现还是编程之美上讲的最清楚,这里我试图用自己的语言来总结一下)

首先是一个重要的规律:对于特定的数n, 所有从1到n上出现1的次数肯定等于个位上1的次数+十位上1的次数+百位上1的次数+千位上1的次数..... 比如

f(3)=1 只有个位上出现1 

f(13)=个位上出现1的有1 11, 十位上有10 11 12 13  = 2 + 4

f(23)=个位11的数量 11 21, 十位上有10 11 12 13 ...19 = 3 + 10

f(33)=个位1的数量 11 21 31, 十位上有10 11 12 13...19 = 4 + 10

f(93)=个位1的数量 有1 11 ... 91, 十位上有10 11 12 13...19 = 10 + 10

f(203)=个位1的数量 11 21..91,101,111,121..191,201 = 21, 十位 10,11,12..19,110...119=20, 百位100,101,199=100

f(12013)=百位上1的数量 100-199,1100-1199,2100-2199,...9100-9199....11100-11199, 总共12*100=1200  即高位数high*当前位数100

f(12113)=百位上1的数量 同上 高位数12*当前位数100=1200, 再加上12100-12113 = 13+1 即低位数low+1, 总共为high*100+low+1

通过上述的例子,可以发现一个规律,就是对于百位上1出现的次数,其受到三个因素影响:

1. 大于百位的,我们称之为高位high,  比如对于12013, 其high为12, 其在百位上出现1的次数受到高位high影响: 100-199, 1100-1199....9100-9199,10100-10199,11100-11199, 因为high的影响,为12*100=high*100

2. 对于百位自身cur,如果百位上的数为0,则没有1,如果等于1,则取决于低位low,比如113, 可以分解为 100-113, 即13+1=low+1. 如果大于1,比如813, 可分解为100-199, 即为100

所以现在需要解决的是然后获得高位high(12013中的12), 当前位cur(12013中的0), 以及低位low(12013中的13)

回到开头那个重要的规律,根据这个规律,我们要用一个变量来代表当前的位数,个位为1,十位为10.。依次类推,用fac来表示,fac由1开始,每处理完一位将fac乘以10,代表移到下一位

 

以12013为例,

高位high的计算方法是 12013/1000 = 12013/(百位fac*10) = 12

当前位cur的计算方法是 (12013/100)%10 = (12013/百位fac)%10 = 120%10 = 0

低位low的计算方法是 12013-(12013/100)*100 = 12013-(12013/百位fac)*百位fac = 12013 - 12000 = 13

 

则百位上1的总数有三种可能性:

1. 百位为0时 total = high*fac = 12*100 = 1200

2. 百位为1时 total = high*fac + low + 1 = 12*100 + 13 + 1

3. 百位为其他时 total = high* fac + fac = (high+1)*fac = (12+1)*100 

 

 1 package com.rui.microsoft; 2  3 public class Test30_Count1 { 4  5     public static void main(String[] args) { 6          7         long current = System.currentTimeMillis(); 8         System.out.println("TOTAL 1: " + countAll(120131111)); 9         System.out.println("TIME USED: " + (System.currentTimeMillis() - current));10         11         current = System.currentTimeMillis();12         System.out.println("TOTAL 1: " + cal(120131111));13         System.out.println("TIME USED: " + (System.currentTimeMillis() - current));14     }15     16     public static int cal(int n){17         int total = 0;18         int fac = 1;19         int high = 0, cur = 0, low = 0;20         21         while(n/fac!=0){22             //12013 -> 12013 - 12000=1323             low = n - (n/fac)*fac;24             //12013 -> (12013/100)%10=025             cur = (n/fac)%10;26             //12013 -> 12013/(100*10)=1227             high = n/(fac*10);28             29             switch(cur){30                 case 0:31                     //百位为032                     //则百位上的1的数量完全取决于高位数33                     total += high*fac;34                     break;35                 case 1:36                     //百位为137                     //则百位上的1的数量取决于高位数和低位数38                     total += high*fac + low + 1;39                     break;40                 default:41                     //百位大于142                     total += (high+1)*fac;43                     break;44             }45             46             fac *= 10;47         }48         49         50         return total;51     }52     53     54     55     public static int countAll(int n){56         if(n <= 0) return 0;57         int total = 0;58         for(int i = 1; i <=n; i++){59             total += count(i);60         }61         return total;62     }63     64     private static int count(int num){65         int total = 0;66         67         while(num>0){68             if(num%10 == 1){69                 total++;70             }71             num = num/10;72         }73         74         return total;75     }76     77 }

 

用传统的方法和上述方法分别计算一个较长的数,比如120131111, 结果如下:

TOTAL 1: 124234672
TIME USED: 1372
TOTAL 1: 124234672
TIME USED: 0

 

可见其性能差距之大

通过此题 我彻底找到了取余的感觉。。。。

  相关解决方案