注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

微软、Google等面试题

剑指Offer:名企面试官精讲典型编程题

 
 
 

日志

 
 

程序员面试题精选100题(25)-在从1到n的正数中1出现的次数[算法]  

2007-04-24 10:40:52|  分类: 数字游戏 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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

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

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

首先我们来看最直观的方法,分别求得1n中每个整数中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作为例子来分析。我们把从121345的所有数字分成两段,即1-12351346-21345

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

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

分析到这里还有一种特殊情况需要注意:前面我们举例子是最高位是一个比1大的数字,此时最高位1出现的次数104(对五位数而言)。但如果最高位是1呢?比如输入12345,从1000012345这些数字中,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);
}

/////////////////////////////////////////////////////////////////////////////
// Find the number of 1 in an integer with radix 10
// Input: strN - a string, which represents an integer
// Output: the number of 1 in n with radix
/////////////////////////////////////////////////////////////////////////////
int NumberOf1(const char* strN)
{
      if(!strN || *strN < '0' || *strN > '9' || *strN == '\0')
            return 0;

      int firstDigit = *strN - '0';
      unsigned int length = static_cast<unsigned int>(strlen(strN));

      // the integer contains only one digit
      if(length == 1 && firstDigit == 0)
            return 0;

      if(length == 1 && firstDigit > 0)
            return 1;

      // suppose the integer is 21345
      // numFirstDigit is the number of 1 of 10000-19999 due to the first digit
      int numFirstDigit = 0;
      // numOtherDigits is the number of 1 01346-21345 due to all digits
      // except the first one
      int numOtherDigits = firstDigit * (length - 1) * PowerBase10(length - 2);
      // numRecursive is the number of 1 of integer 1345
      int numRecursive = NumberOf1(strN + 1);

      // if the first digit is greater than 1, suppose in integer 21345
      // number of 1 due to the first digit is 10^4. It's 10000-19999
      if(firstDigit > 1)
            numFirstDigit = PowerBase10(length - 1);

      // if the first digit equals to 1, suppose in integer 12345
      // number of 1 due to the first digit is 2346. It's 10000-12345
      else if(firstDigit == 1)
            numFirstDigit = atoi(strN + 1) + 1;

      return numFirstDigit + numOtherDigits + numRecursive;
}

/////////////////////////////////////////////////////////////////////////////
// Calculate 10^n
/////////////////////////////////////////////////////////////////////////////
int PowerBase10(unsigned int n)
{
      int result = 1;
      for(unsigned int i = 0; i < n; ++ i)
            result *= 10;

      return result;
}

本文已经收录到《剑指Offer——名企面试官精讲典型编程题》一书中,有改动,书中的分析讲解更加详细。欢迎关注。

本题已被九度Online Judge系统收录,欢迎读者移步到http://ac.jobdu.com/hhtproblems.php在线测试自己的代码。

博主何海涛对本博客文章享有版权。网络转载请注明出处http://zhedahht.blog.163.com/。整理出版物请和作者联系。

  评论这张
 
阅读(25715)| 评论(47)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017