Lintcode3DigitCountssolution題解-創(chuàng)新互聯(lián)

【題目描述】

創(chuàng)新互聯(lián)主打移動(dòng)網(wǎng)站、網(wǎng)站建設(shè)、成都網(wǎng)站制作、網(wǎng)站改版、網(wǎng)絡(luò)推廣、網(wǎng)站維護(hù)、國際域名空間、等互聯(lián)網(wǎng)信息服務(wù)，為各行業(yè)提供服務(wù)。在技術(shù)實(shí)力的保障下，我們?yōu)榭蛻舫兄Z穩(wěn)定，放心的服務(wù)，根據(jù)網(wǎng)站的內(nèi)容與功能再?zèng)Q定采用什么樣的設(shè)計(jì)。最后，要實(shí)現(xiàn)符合網(wǎng)站需求的內(nèi)容、功能與設(shè)計(jì)，我們還會(huì)規(guī)劃穩(wěn)定安全的技術(shù)方案做保障。

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)在來考慮百位上出現(xiàn)2的次數(shù)，即，從0到abcde的數(shù)中， 有多少個(gè)數(shù)的百位上是2。分析完它，就可以用同樣的方法去計(jì)算個(gè)位，十位，千位， 萬位等各個(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è)。

上面兩步綜合起來，可以得到以下結(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ù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

分享標(biāo)題：Lintcode3DigitCountssolution題解-創(chuàng)新互聯(lián)
URL網(wǎng)址：http://muchs.cn/article16/djehgg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供標(biāo)簽優(yōu)化、網(wǎng)站收錄、品牌網(wǎng)站設(shè)計(jì)、動(dòng)態(tài)網(wǎng)站、企業(yè)建站、App開發(fā)

廣告

聲明：本網(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í)需注明來源： 創(chuàng)新互聯(lián)