Lintcode3 Digit Counts solution 題解

【題目描述】

Count the number of k's between 0 and n. k can be 0 - 9.

計算數(shù)字k在0到n中的出現(xiàn)的次數(shù)，k可能是0~9的一個值。

【題目鏈接】

http://www.lintcode.com/en/problem/digit-counts/

【題目解析】

方法一： Brute Force, 0到n個數(shù)挨個算過去。最大的問題就是效率，當n非常大時，就需要很長的運行時間。

方法二：當某一位的數(shù)字小于i時，那么該位出現(xiàn)i的次數(shù)為：更高位數(shù)字x當前位數(shù)；當某一位的數(shù)字等于i時，那么該位出現(xiàn)i的次數(shù)為：更高位數(shù)字x當前位數(shù)+低位數(shù)字+1；當某一位的數(shù)字大于i時，那么該位出現(xiàn)i的次數(shù)為：(更高位數(shù)字+1)x當前位數(shù)

假設(shè)一個5位數(shù)N=abcde，我們現(xiàn)在來考慮百位上出現(xiàn)2的次數(shù)，即，從0到abcde的數(shù)中， 有多少個數(shù)的百位上是2。分析完它，就可以用同樣的方法去計算個位，十位，千位， 萬位等各個位上出現(xiàn)2的次數(shù)。

當百位c為0時，比如說12013，0到12013中哪些數(shù)的百位會出現(xiàn)2？我們從小的數(shù)起， 200~299, 1200~1299, 2200~2299, … , 11200~11299, 也就是固定低3位為200~299，

然后高位依次從0到11，共12個。再往下12200~12299 已經(jīng)大于12013，因此不再往下。所以，當百位為0時，百位出現(xiàn)2的次數(shù)只由更高位決定， 等于更高位數(shù)字(12)x當前位數(shù)(100)=1200個。

當百位c為1時，比如說12113。分析同上，并且和上面的情況一模一樣。 最大也只能到11200~11299，所以百位出現(xiàn)2的次數(shù)也是1200個。

上面兩步綜合起來，可以得到以下結(jié)論：

當某一位的數(shù)字小于2時，那么該位出現(xiàn)2的次數(shù)為：更高位數(shù)字x當前位數(shù)

當百位c為2時，比如說12213。那么，我們還是有200~299, 1200~1299, 2200~2299, … , 11200~11299這1200個數(shù)，他們的百位為2。但同時，還有一部分12200~12213， 共14個(低位數(shù)字+1)。所以，當百位數(shù)字為2時， 百位出現(xiàn)2的次數(shù)既受高位影響也受低位影響，結(jié)論如下：

當某一位的數(shù)字等于2時，那么該位出現(xiàn)2的次數(shù)為：更高位數(shù)字x當前位數(shù)+低位數(shù)字+1

當百位c大于2時，比如說12313，那么固定低3位為200~299，高位依次可以從0到12， 這一次就把12200~12299也包含了，同時也沒低位什么事情。因此出現(xiàn)2的次數(shù)是： (更高位數(shù)字+1)x當前位數(shù)。結(jié)論如下：

當某一位的數(shù)字大于2時，那么該位出現(xiàn)2的次數(shù)為：(更高位數(shù)字+1)x當前位數(shù)

【參考答案】

http://www.jiuzhang.com/solutions/digit-counts/