30. 在從1到n的整數中1出現的次數
題目：輸入一個整數n，求從1到n 這n個整數的十進制表示中1出現的次數。
例如輸入12，從1到12這些整數中包含1的數字有1，10，11 和12，1 一共出現了5 次。
分析：這是一道廣為流傳的google 面試題

思路：

第一反應是遍歷這N個數，然后對每個正數n不斷用10取余來求各個位上1的次數，同理對每個數求1出現的次數并累加，但這種方法的時間復雜度是o(n)，當n值很高時耗時太久

第二個思路是能不能通過數學的方法找到n上所有1的次數 (自己實在是想不出來，先從網上搜了一下，最后發現還是編程之美上講的最清楚，這里我試圖用自己的語言來總結一下)

首先是一個重要的規律：對于特定的數n, 所有從1到n上出現1的次數肯定等于個位上1的次數+十位上1的次數+百位上1的次數+千位上1的次數..... 比如

f(3)=1 只有個位上出現1 

f(13)=個位上出現1的有1 11, 十位上有10 11 12 13  = 2 + 4

f(23)=個位11的數量 11 21, 十位上有10 11 12 13 ...19 = 3 + 10

f(33)=個位1的數量 11 21 31, 十位上有10 11 12 13...19 = 4 + 10

f(93)=個位1的數量 有1 11 ... 91, 十位上有10 11 12 13...19 = 10 + 10

f(203)=個位1的數量 11 21..91,101,111,121..191,201 = 21, 十位 10,11,12..19,110...119=20, 百位100,101,199=100

f(12013)=百位上1的數量 100-199,1100-1199,2100-2199,...9100-9199....11100-11199, 總共12*100=1200  即高位數high*當前位數100

f(12113)=百位上1的數量 同上 高位數12*當前位數100=1200, 再加上12100-12113 = 13+1 即低位數low+1, 總共為high*100+low+1

通過上述的例子，可以發現一個規律，就是對于百位上1出現的次數，其受到三個因素影響：

1. 大于百位的，我們稱之為高位high,  比如對于12013, 其high為12, 其在百位上出現1的次數受到高位high影響: 100-199, 1100-1199....9100-9199,10100-10199,11100-11199, 因為high的影響，為12*100=high*100

2. 對于百位自身cur，如果百位上的數為0，則沒有1，如果等于1，則取決于低位low，比如113, 可以分解為 100-113, 即13+1=low+1. 如果大于1，比如813, 可分解為100-199, 即為100

所以現在需要解決的是然后獲得高位high(12013中的12), 當前位cur(12013中的0), 以及低位low(12013中的13）

回到開頭那個重要的規律，根據這個規律，我們要用一個變量來代表當前的位數，個位為1，十位為10.。依次類推，用fac來表示，fac由1開始，每處理完一位將fac乘以10，代表移到下一位

以12013為例，

高位high的計算方法是 12013/1000 = 12013/(百位fac*10) = 12

當前位cur的計算方法是 (12013/100)%10 = (12013/百位fac)%10 = 120%10 = 0

低位low的計算方法是 12013-(12013/100)*100 = 12013-(12013/百位fac)*百位fac = 12013 - 12000 = 13

則百位上1的總數有三種可能性:

1. 百位為0時 total = high*fac = 12*100 = 1200

2. 百位為1時 total = high*fac + low + 1 = 12*100 + 13 + 1

3. 百位為其他時 total = high* fac + fac = (high+1)*fac = (12+1)*100 

 1 package com.rui.microsoft; 2  3 public class Test30_Count1 { 4  5     public static void main(String[] args) { 6          7         long current = System.currentTimeMillis(); 8         System.out.)); 9         System.out.println("TIME USED: " + (System.currentTimeMillis() - current));10         11         current = System.currentTimeMillis();12         System.out.println("TOTAL 1: " + cal(120131111));13         System.out.println("TIME USED: " + (System.currentTimeMillis() - current));14     }15     16     public static int cal(int n){17         int total = 0;18         int fac = 1;19         int high = 0, cur = 0, low = 0;20         21         while(n/fac!=0){22             //12013 -> 12013 - 12000=1323             low = n - (n/fac)*fac;24             //12013 -> (12013/100)%10=025             cur = (n/fac)%10;26             //12013 -> 12013/(100*10)=1227             high = n/(fac*10);28             29             switch(cur){30                 case 0:31                     //百位為032                     //則百位上的1的數量完全取決于高位數33                     total += high*fac;34                     break;35                 case 1:36                     //百位為137                     //則百位上的1的數量取決于高位數和低位數38                     total += high*fac + low + 1;39                     break;40                 default:41                     //百位大于142                     total += (high+1)*fac;43                     break;44             }45             46             fac *= 10;47         }48         49         50         return total;51     }52     53     54     55     public static int countAll(int n){56         if(n <= 0) return 0;57         int total = 0;58         for(int i = 1; i <=n; i++){59             total += count(i);60         }61         return total;62     }63     64     private static int count(int num){65         int total = 0;66         67         while(num>0){68             if(num%10 == 1){69                 total++;70             }71             num = num/10;72         }73         74         return total;75     }76     77 }

用傳統的方法和上述方法分別計算一個較長的數，比如120131111， 結果如下：

TOTAL 1: 124234672
TIME USED: 1372
TOTAL 1: 124234672
TIME USED: 0

可見其性能差距之大

通過此題 我徹底找到了取余的感覺。。。。