给定N，依次写下1,2,3,4......N，求数字1出现的个数，比如给定N为13，则序列为1,2,3,4,5,6,7,8,9,10,11,12,13，在这个序列中，数字1一共出现了6次。
开门见山，还是直接分析《编程之美》上的方法：
对于某个N，假如它是5位数
abcde，则我们考察百位数字c的情况，
1）若c = 0，比如12023，则列出的所有数字中，百位出现1的有
100-199，1100-1199, 2100-2199, ... ,10100-10199,11100-11199，总共有12 * 100 = 1200个12）若c = 1，比如12123，则列出的所有数字中，百位出现1的有
100-199，1100-1199, 2100-2199, ... ,10100-10199,11100-11199,12100-12123，总共有12 * 100 + (23 + 1) = 1224个13）若c > 1，比如12223，则列出的所有数字中，百位出现1的有
100-199，1100-1199, 2100-2199, ... ,10100-10199,11100-11199,12100-12199，总共有(12 + 1) * 100 = 1300个1
说到这儿可以总结规律了，对于N =
XkXk-1...Xi+1XiXi-1...X2X1，
1）若Xi = 0，则第i位上出现1的个数为
XkXk-1...Xi+1 * 10
i-1
2）若Xi = 1，则第i位上出现1的个数为
XkXk-1...Xi+1 * 10
i-1 +
Xi-1...X2X1 +1
3）若Xi > 1，则第i位上出现1的个数为 (
XkXk-1...Xi+1 + 1) * 10
i-1
据此可以写代码如下：
1 int sum1s(int n) {
2 int factor = 1;
3 int lower = 0;
4 int cur = 0;
5 int higher = 0;
6 int count = 0;
7 while (n >= factor) {
8 higher = n / (factor * 10);
9 cur = (n / factor) % 10;
10 lower = n % factor;
11 switch (cur) {
12 case 0:
13 count += higher * factor;
14 break;
15 case 1:
16 count += higher * factor + 1 + lower;
17 break;
18 default:
19 count += (higher + 1) * factor;
20 break;
21 }
22 factor *= 10;
23 }
24 return count;
25 }
这种题一定要仔细分析，找到规律，就迎刃而解了。
posted on 2012-09-04 17:08
myjfm 阅读(1628)
评论(0) 编辑 收藏 引用 所属分类:
算法基础