软件水平 > 初级资格 > 程序员 > 文章内容

软件水平考试程序员精选题(13)

2017-8-19编辑:daibenhua

  在从1到n的正数中1出现的次数

  题目:输入一个整数n,求从1到n这n个整数的十进制表示中1出现的次数。

  例如输入12,从1到12这些整数中包含1 的数字有1,10,11和12,1一共出现了5次。

  分析:这是一道广为流传的google面试题。用最直观的方法求解并不是很难,但遗憾的是效率不是很高;而要得出一个效率较高的算法,需要比较强的分析能力,并不是件很容易的事情。当然,google的面试题中简单的也没有几道。

  首先我们来看最直观的方法,分别求得1到n中每个整数中1出现的次数。而求一个整数的十进制表示中1出现的次数,就和本面试题系列的第22题很相像了。我们每次判断整数的个位数字是不是1。如果这个数字大于10,除以10之后再判断个位数字是不是1。基于这个思路,不难写出如下的代码:

  int NumberOf1(unsigned int n);

  /////////////////////////////////////////////////////////////////////////////

  // Find the number of 1 in the integers between 1 and n

  // Input: n - an integer

  // Output: the number of 1 in the integers between 1 and n

  /////////////////////////////////////////////////////////////////////////////

  int NumberOf1BeforeBetween1AndN_Solution1(unsigned int n)

  {

  int number = 0;

  // Find the number of 1 in each integer between 1 and n

  for(unsigned int i = 1; i <= n; ++ i)

  number += NumberOf1(i);

  return number;

  }

  /////////////////////////////////////////////////////////////////////////////

  // Find the number of 1 in an integer with radix 10

  // Input: n - an integer

  // Output: the number of 1 in n with radix

  /////////////////////////////////////////////////////////////////////////////

  int NumberOf1(unsigned int n)

  {

  int number = 0;

  while(n)

  {

  if(n % 10 == 1)

  number ++;

  n = n / 10;

  }

  return number;

  }

  这个思路有一个非常明显的缺点就是每个数字都要计算1在该数字中出现的次数,因此时间复杂度是O(n)。当输入的n非常大的时候,需要大量的计算,运算效率很低。我们试着找出一些规律,来避免不必要的计算。

  我们用一个稍微大一点的数字21345作为例子来分析。我们把从1到21345的所有数字分成两段,即1-1235和1346-21345。

  先来看1346-21345中1出现的次数。1的出现分为两种情况:一种情况是1出现在最高位(万位)。从1到21345的数字中,1出现在10000-19999这10000个数字的万位中,一共出现了10000(104)次;另外一种情况是1出现在除了最高位之外的其他位中。例子中1346-21345,这20000个数字中后面四位中1出现的次数是2000次(2*103,其中2的第一位的数值,103是因为数字的后四位数字其中一位为1,其余的三位数字可以在0到9这10个数字任意选择,由排列组合可以得出总次数是2*103)。

  至于从1到1345的所有数字中1出现的次数,我们就可以用递归地求得了。这也是我们为什么要把1-21345分为1-1235和1346-21345两段的原因。因为把21345的最高位去掉就得到1345,便于我们采用递归的思路。

  分析到这里还有一种特殊情况需要注意:前面我们举例子是最高位是一个比1大的数字,此时最高位1出现的次数104(对五位数而言)。但如果最高位是1呢?比如输入12345,从10000到12345这些数字中,1在万位出现的次数就不是104次,而是2346次了,也就是除去最高位数字之后剩下的数字再加上1。

  基于前面的分析,我们可以写出以下的代码。在参考代码中,为了编程方便,我把数字转换成字符串了。

  #include "string.h"

  #include "stdlib.h"

  int NumberOf1(const char* strN);

  int PowerBase10(unsigned int n);

  /////////////////////////////////////////////////////////////////////////////

  // Find the number of 1 in an integer with radix 10

  // Input: n - an integer

  // Output: the number of 1 in n with radix

  /////////////////////////////////////////////////////////////////////////////

  int NumberOf1BeforeBetween1AndN_Solution2(int n)

  {

  if(n <= 0)

  return 0;

  // convert the integer into a string

  char strN[50];

  sprintf(strN, "%d", n);

  return NumberOf1(strN);

  }

  /////////////////////////////////////////////////////////////////////////////

软件水平考试程序员精选题(12)

热点推荐

登录注册
触屏版电脑版网站地图