“1”的个数

设计思路

　　最笨的方法就是从1到N判断每一个数含有的“1”的个数，逐次相加。问题就在于当N特别大的时候，时间复杂度太高。这时老师给我们一个提示，就是找出“1”的个数和它各个位置上的数字的关系，这样就简化了问题，降低了时间复杂度。首先从个位开始，找出当前位数、高位数和低位数，然后进行判断，当前位数如果为0，出现“1”的次数由高位决定；如果为1，出现“1”的次数由高位和低位共同决定；如果大于1，出现“1”的次数由高位决定。

源程序代码

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int count1(int n)
 5 {
 6     if (n <= 0)
 7     {
 8         return 0;
 9     }
10     int num = 0;
11     int factor = 1;
12     while(n / factor != 0)
13     {
14         int lowerNum = n - n / factor * factor;//低位数
15         int currentNum = (n / factor) % 10;//当前位数
16         int highNum = n / (factor * 10);//高位数
17         if (currentNum == 0)
18         {// 如果为0，出现1的次数由高位决定
19             num += highNum * factor;
20         }
21         else if (currentNum == 1)
22         {// 如果为1，出现1的次数由高位和低位决定
23             num += highNum * factor + lowerNum + 1;
24         }
25         else
26         {// 如果大于1，出现1的次数由高位决定
27             num += (highNum + 1) * factor;
28         }
29         factor *= 10;
30     }
31     return num;
32 }
33 
34 void main()
35 {
36     int n;
37     for (n = 2147483647;n > 0;n--)
38     {
39         if (n==count1(n))
40         {
41             cout<<n<<endl;
42             exit(0);
43         }
44     }
45 }

运行结果截图

编程总结

解决问题时，要注意找到规律。有些问题是有规律的，老师一直教导我们不能一味的编程，那样只能越搞越乱，先琢磨出问题的本质所在，再进行编程。