資訊專欄INFORMATION COLUMN
摘要：題目要求計(jì)算所有小于等于的正整數(shù)中數(shù)字的個(gè)數(shù)。比如比小的正整數(shù)中包含的有，一共有個(gè)。因此，我們需要用更好的方法，減少這種方法的浪費(fèi)。其實(shí)等價(jià)于中的的個(gè)數(shù)。
題目要求
Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n. For example: Given n = 13, Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.
計(jì)算所有小于等于n的正整數(shù)中數(shù)字1的個(gè)數(shù)。
比如比13小的正整數(shù)中包含1的有1,10,11,12,13，一共有6個(gè)1。
如果使用暴力循環(huán)的話，那么我們只需要遍歷所有小于n的正整數(shù)，計(jì)算該正整數(shù)中包含幾個(gè)1并將返回這些結(jié)果的和。但是，這種方法浪費(fèi)了很多不必要的計(jì)算。比如在小于n的正整數(shù)中，有很多甚至都一個(gè)1都沒(méi)有。因此，我們需要用更好的方法，減少這種方法的浪費(fèi)。
我們隨意找一個(gè)數(shù)來(lái)入手，假設(shè)現(xiàn)在n為52，那么52下含有的1實(shí)際上等于50~52 + 1~49中有的1，也就等價(jià)于0~2 + 1~49中含有的1。
在這里我們很清楚的知道，當(dāng)n<10時(shí)，只有1個(gè)1。因此0~2只有1個(gè)1。
我們?cè)賮?lái)拆解1~49。
1~49其實(shí)等價(jià)于40~49 + 30~39 + 20~29 + 10~19 + 1~9中的1的個(gè)數(shù)。我們?cè)俜治鲆幌戮蜁?huì)發(fā)現(xiàn)，40~49, 30~39 , 20~29, 0~9中的1的個(gè)數(shù)是相同的！而特殊的情況是10~19，它的1的數(shù)量其實(shí)等于10 + 0~9。
總結(jié)一下我們知道countDigitOne(52) = countDigitOne(2) + countDigitOne(9) * 5 + 10。
這里其實(shí)還有一個(gè)特殊情況，就是當(dāng)最高位恰好為1的時(shí)候，舉個(gè)例子135。那么100~135等價(jià)于36+0~35個(gè)1，那么countDigitOne(135) = 36 + countDigitOne(35) + countDigitOne(99)。
整理為代碼如下：
public int countDigitOne(int n) {
if(n <= 0) return 0;
if(n < 10) return 1;
int count = 1;
while(n / count > 9){
count *= 10;
}
if(n / count == 1){
return n % count + 1 + countDigitOne(n%count) + countDigitOne(count-1);
}else{
return countDigitOne(n % count) + count + (n/count) * countDigitOne(count-1);
}
}
想要了解更多開(kāi)發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/70939.html
摘要：遞歸復(fù)雜度思路每次將一個(gè)數(shù)拆分成兩部分考慮，并考慮當(dāng)前最高是不是比如，將數(shù)拆分成，和，這兩部分分別計(jì)算。每次抹去高位，觀察重復(fù)情況。代碼代表位數(shù)，代表最高的值除了高位的剩余部分 LeetCode[23] Number of Digit One Given an integer n, count the total number of digit 1 appearing in alln...
摘要：題目給一個(gè)數(shù)求從到所有數(shù)中數(shù)字在各個(gè)位上出現(xiàn)的總次數(shù)。解法可以做循環(huán)從到挨個(gè)找。更好的是用歸納法總結(jié)出出現(xiàn)的次數(shù)的規(guī)律。 題目：Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n. For example:...
摘要：只有大于左邊界才部分包含，且只有大于右邊界的數(shù)才完整包含，這些中多余的。對(duì)于而言，部分包含用余數(shù)做，完整包含用進(jìn)位后的商做。逐位向上累加，可得結(jié)果。千位萬(wàn)位，大致如此。例如個(gè)位十位百位千位 Problem Given an integer n, count the total number of digit 1 appearing in all non-negative integer...
摘要：但是，往往會(huì)有可以優(yōu)化的空間。假設(shè)我們用來(lái)記錄子數(shù)組之間，第一個(gè)取數(shù)字的玩家和第二個(gè)取數(shù)字的玩家之間最大的差距。再考慮初始情況，即當(dāng)數(shù)組長(zhǎng)度為時(shí)，可以得知此時(shí)玩家一和玩家二之間的差距即為該數(shù)組元素的值。 題目要求 Given an array of scores that are non-negative integers. Player 1 picks one of the numb...
摘要：不過(guò)這里有個(gè)小技巧，因?yàn)槲覀冎灰?，所以不用完全模擬加法的所有規(guī)則一個(gè)數(shù)如果不是，那加以后不會(huì)對(duì)其他位產(chǎn)生影響。 Plus One Given a non-negative number represented as an array of digits, plus one to the number. The digits are stored such that the most...
閱讀 433·2019-08-29 12:44
閱讀 3011·2019-08-26 17:49
閱讀 2433·2019-08-26 13:40
閱讀 1185·2019-08-26 13:39
閱讀 3663·2019-08-26 11:59
閱讀 1827·2019-08-26 10:59
閱讀 2465·2019-08-23 18:33
閱讀 2697·2019-08-23 18:30
