如N=12，则f(12)=5，因为1,2,3,4,5,6,7,8,9,10,11,12共出现5次“1”。
当年第一次看这个题的时候觉得无从下手，这次到迅速有了思路，还是有进步的嘛。
思路就是分别统计个位、十位、百位…上的1的数目。先考虑个位上的1的数目，个位上的1是每10个数中会出现1次的，即1-10出现一次，11-20出现一次…因此可以计算N/10，对于N%10的部分，只要N%10>=1，就有一个1，也只能有一个1。同理再考虑十位上的1，十位上的1是每100个数字中会出现10次，如1-100出现10次（10-19），101-200出现10次（110-119）…因此可以计算N/100*10，对于N%100的部分，只有在10-19之间会出现1，因此可以分情况讨论。百位上、千位上的情况依此类推，再举一例，说一下千位上的情况吧，对于千位上的1，是每10000个数里出现1000次，例如1-10000里出现1000次（1000-1999），10001-20000里出现1000次（11000-11999）…因此可以计算N/10000*1000，对于N%10000的部分，只有在1000-1999之间会出现千位上的1，同样分情况讨论之。
代码如下：
1: __int64 func(__int64 N)
2: {
3: __int64 _disibledevent=> 4: __int64 factor = 10;
5: __int64 a,b,c;
6: do
7: {
8: a = N/factor;
9: b = N%factor;
10: c = a*(factor/10);
11:
12: _disibledevent=> 13:
14: if (b >= factor/10)
15: {
16: if (b > 2*(factor/10) - 1)
17: {
18: _disibledevent=> 19: }
20: else
21: {
22: _disibledevent=> 23: }
24: }
25: factor *= 10;
26: } while (a != 0);
27:
28: return _disibledevent=> 29: }
最新评论