【面试题32】从1到n整数中1出现的次数

【题目描述】

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

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

【解决方案】

解法一：不考虑时间复杂度

我的代码实现，仅供参考：

 1         public static int NumOfOneFromOneToN(int n)
 2         {
 3             int result = 0;
 4 
 5             for (int i = 0; i <= n;i++ )
 6             {
 7                 int temp = i;
 8                 while (temp != 0)
 9                 {
10                     if (temp % 10 == 1)
11                         result++;
12                     temp /= 10;
13                 }
14             }
15 
16             return result;
17         }

解法二：从数字规律着手明显提高时间效率的解法

我的代码实现，仅供参考：

 1         public static int NumberOf1Between1AndN(int n)
 2         {
 3             if (n <= 0)
 4                 return 0;
 5 
 6             string str = n.ToString();
 7 
 8             return NumberOf1(str);
 9         }
10 
11         public static int NumberOf1(string str)
12         {
13             int first = str[0] - '0';
14 
15             int length = str.Length;
16 
17             if (length == 1 && first == 0)
18                 return 0;
19 
20             if (length == 1 && first > 0)
21                 return 1;
22 
23             int numFirstDigit = 0;
24             if (first > 1)
25                 numFirstDigit = (int)Math.Pow(10, length - 1);
26             else if (first == 1)
27                 numFirstDigit = (Convert.ToInt32(str.Substring(1))) + 1;
28 
29             int numOtherDigits = (int)(first * (length - 1) * Math.Pow(10, length - 2));
30 
31             int numRecursive = NumberOf1(str.Substring(1));
32 
33             return numFirstDigit + numOtherDigits + numRecursive;
34         }