【題目描述】

惠來(lái)網(wǎng)站建設(shè)公司創(chuàng)新互聯(lián),惠來(lái)網(wǎng)站設(shè)計(jì)制作，有大型網(wǎng)站制作公司豐富經(jīng)驗(yàn)。已為惠來(lái)上1000家提供企業(yè)網(wǎng)站建設(shè)服務(wù)。企業(yè)網(wǎng)站搭建\成都外貿(mào)網(wǎng)站建設(shè)公司要多少錢，請(qǐng)找那個(gè)售后服務(wù)好的惠來(lái)做網(wǎng)站的公司定做！

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

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

【題目鏈接】

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

【題目解析】

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

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

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

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

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

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

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

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

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

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

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

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

【參考答案】

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

網(wǎng)頁(yè)題目：Lintcode3DigitCountssolution題解
當(dāng)前路徑：http://jinyejixie.com/article32/pshipc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供企業(yè)建站、網(wǎng)站制作、App開發(fā)、關(guān)鍵詞優(yōu)化、網(wǎng)站設(shè)計(jì)公司、響應(yīng)式網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)