编程之美 2.4 1的数目

题目：

给定一个10进制整数N，从1开始，到N的所有整数中，1共出现了多少次。

解法一：

暴力法，从1开始遍历，并计算每个1出现的次数：

时间复杂度为O(n)x计算一个整数中1的个数的时间复杂度=O(n*logn)

 1 #include "iostream"
 2 
 3 using namespace std;
 4 
 5 int count1(int n)
 6 {
 7     int num = 0;
 8     while (n)
 9     {
10         if(n%10==1)
11             num++;
12         n /= 10;
13     }
14     return num;
15 }
16 
17 int main()
18 {
19     int n,ans;
20     while (cin >> n)
21     {
22         ans = 0;
23         for (int i = 1; i <= n; i++)
24         {
25             ans += count1(i);
26         }
27 
28         cout << ans <<endl;
29     }
30     system("pause");
31 }

法二：

可以发现1出现的次数，受当前位数高位数和低位数的影响。

如果当前位数为1，则当前位数1出现的次数是高*位+低+1

如果当前位数为0，则当前位数1出现的次数是高*位

如果当前位数为x（非 01），则当前位数1出现的次数是（高+1）*位

 1 #include "iostream"
 2 
 3 using namespace std;
 4 
 5 int sum(int n)
 6 {
 7     int count = 0;
 8     int factor = 1;
 9     int higherNum = 0;
10     int lowerNum = 0;
11     int nowNum = 0;
12 
13     while (n/factor)
14     {
15         lowerNum = n - n / factor*factor;   //相当于把当前位后面的都至为0
16         nowNum = (n / factor) % 10;
17         higherNum = n / (factor * 10);
18         switch (nowNum)
19         {
20         case 0:
21             count += higherNum*factor; break;
22         case 1:
23             count += higherNum*factor + lowerNum + 1; break;
24         default:
25             count += (higherNum + 1)*factor;
26             break;
27         }
28         factor *= 10;
29     }
30     return count;
31 }
32 
33 int main()
34 {
35     int n,ans;
36     while (cin >> n)
37     {
38         cout << sum(n) <<endl;
39     }
40     system("pause");
41 }