面试题:计算0到n的数中有多少个2

例如给出n=100,那么就是计算0到100这么多个数中有多少个2.

首先要搞清楚2是怎么来的(这话怎么听起来不对劲?):

有2个来源:

1 个位来源:12,32,42,82,92,22等,其中的22可以先计算个位的2,然后十位的2留待第二个情况处理

2 十位来源:20,21,22,23,24,25,26,27,28,29共10个

 

举例1000,

1 个位2出现在,2,12,22,32,42,52,62,72,82,92共10个;也出现在102,112,122,132,142,152,162,172,182,192;202,212,…992等共100个

2 十位2出现在:20,21,22,23,24,25,26,27,28,29; 120,121,122,123,124,125,126,127,128,129;,220,221,222,223,…共100个

3 还有百位的:201,202,203,204,205,206,207,208,209,210,211,212…299共一百 个。

所以总共是300个。

但是100为的情况可以当做是10位的情况考虑,需要一点窍门。分三种情况计算。

 

这点窍门还是直接上程序比较好学会吧,如果解说,我觉得真是太啰嗦了,好像本书作者那样,老实说我真不知道他说啥,后来是直接看他的代码看懂的。

而且本题的难点还真不在这个思路上面,还是把思想优雅地转换成为代码这一步是最难的,就跟数字发音的题目那样。

还是那句话:会思路,和把思路转换程序差不多是两种能力来的。所以某些人老是强调思路是最重要的,但是这句话最多对了一半,因为那得看什么题目。

下面给出暴力法,和上面例子那么计算的方法:

 

[cpp][/cpp] view plaincopyprint?

  1. //暴力法
  2. int numOf2s(int i)
  3. {
  4.     int count = 0;
  5.     while (i>0)
  6.     {
  7.         if (i%10 == 2) count++;
  8.         i /= 10;
  9.     }
  10.     return count;
  11. }
  12. int numOf2sInRange(int n)
  13. {
  14.     int count = 0;
  15.     for (int i = 2; i <= n; i++)
  16.     {
  17.         count += numOf2s(i);
  18.     }
  19.     return count;
  20. }
  21. //分块计算法
  22. int count2sInRangeAtDigit(int num, int d)
  23. {
  24.     int powOf10 = (int) pow(10, d);
  25.     int nextPowOf10 = 10 * powOf10;
  26.     int right = num % powOf10;
  27.     int roundDown = num – num % nextPowOf10;
  28.     int roundUp = roundDown + nextPowOf10;
  29.     int digit = (num / powOf10) %10;
  30.     //相当于计算个位的2,如:每十位就有一个2
  31.     if (digit < 2)
  32.     {
  33.         return roundDown / 10;
  34.     }
  35.     //相当于计算10位的2,如:有多少个20,21,22,23的十位里面有3+1个2
  36.     else if (digit == 2)
  37.     {
  38.         return roundDown / 10 + right +1;
  39.     }
  40.     //超过了2,那么10位的2肯定有10个,如30以下的:20,21,22,23,…,29有十个2
  41.     else
  42.     {
  43.         return roundUp / 10;
  44.     }
  45. }
  46. int count2sInRange(int num)
  47. {
  48.     int c = 0;
  49.     ostringstream ss;
  50.     ss<<num;
  51.     int len = ss.str().length();
  52.     for (int digit = 0; digit < len; digit++)
  53.     {
  54.         c += count2sInRangeAtDigit(num, digit);
  55.     }
  56.     return c;
  57. }
  58. int main()
  59. {
  60.     int tar = 7;
  61.     int cand[] = {1,2,3,0,3,2,0,3,1,4,5,3,2,7,5,3,0,1,2,1,3,4,6,8,1,8};
  62.     cout<<numOf2sInRange(1000)<<endl;
  63.     cout<<count2sInRange(1000)<<endl;
  64.     system(“pause”);
  65.     return 0;
  66. }

 

运行结果:

上面是暴力法,下面是分块计算的方法,结果是一样的。不过好像暴力法超过9位数就无法计算出来了。

注意:计算INT_MAX的时候还有可能溢出处理方法是改成long long保存结果就可以了。很简单,本文就不给出了。O(∩_∩)O~

标签