微軟算法100題30在從1到n的整數(shù)中1出現(xiàn)的次數(shù)

2019-11-14 15:16:28

字體：大中小

供稿：網(wǎng)友

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

思路：

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

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

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

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

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

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

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

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

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

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

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

通過上述的例子，可以發(fā)現(xiàn)一個規(guī)律，就是對于百位上1出現(xiàn)的次數(shù)，其受到三個因素影響：

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

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

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

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

以12013為例，

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

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

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

則百位上1的總數(shù)有三種可能性:

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的數(shù)量完全取決于高位數(shù)33                     total += high*fac;34                     break;35                 case 1:36                     //百位為137                     //則百位上的1的數(shù)量取決于高位數(shù)和低位數(shù)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 }