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

 在从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