給定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 閱讀(1692)
評論(0) 編輯 收藏 引用 所屬分類:
算法基礎