摘要:題目要求計算所有小于等于的正整數中數字的個數。比如比小的正整數中包含的有,一共有個。因此,我們需要用更好的方法,減少這種方法的浪費。其實等價于中的的個數。
題目要求
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.
計算所有小于等于n的正整數中數字1的個數。
比如比13小的正整數中包含1的有1,10,11,12,13,一共有6個1。
如果使用暴力循環的話,那么我們只需要遍歷所有小于n的正整數,計算該正整數中包含幾個1并將返回這些結果的和。但是,這種方法浪費了很多不必要的計算。比如在小于n的正整數中,有很多甚至都一個1都沒有。因此,我們需要用更好的方法,減少這種方法的浪費。
我們隨意找一個數來入手,假設現在n為52,那么52下含有的1實際上等于50~52 + 1~49中有的1,也就等價于0~2 + 1~49中含有的1。
在這里我們很清楚的知道,當n<10時,只有1個1。因此0~2只有1個1。
我們再來拆解1~49。
1~49其實等價于40~49 + 30~39 + 20~29 + 10~19 + 1~9中的1的個數。我們再分析一下就會發現,40~49, 30~39 , 20~29, 0~9中的1的個數是相同的!而特殊的情況是10~19,它的1的數量其實等于10 + 0~9。
總結一下我們知道countDigitOne(52) = countDigitOne(2) + countDigitOne(9) * 5 + 10。
這里其實還有一個特殊情況,就是當最高位恰好為1的時候,舉個例子135。那么100~135等價于36+0~35個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); } }
想要了解更多開發技術,面試教程以及互聯網公司內推,歡迎關注我的微信公眾號!將會不定期的發放福利哦~
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/70939.html
摘要:遞歸復雜度思路每次將一個數拆分成兩部分考慮,并考慮當前最高是不是比如,將數拆分成,和,這兩部分分別計算。每次抹去高位,觀察重復情況。代碼代表位數,代表最高的值除了高位的剩余部分 LeetCode[23] Number of Digit One Given an integer n, count the total number of digit 1 appearing in alln...
摘要:題目給一個數求從到所有數中數字在各個位上出現的總次數。解法可以做循環從到挨個找。更好的是用歸納法總結出出現的次數的規律。 題目: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:...
摘要:只有大于左邊界才部分包含,且只有大于右邊界的數才完整包含,這些中多余的。對于而言,部分包含用余數做,完整包含用進位后的商做。逐位向上累加,可得結果。千位萬位,大致如此。例如個位十位百位千位 Problem Given an integer n, count the total number of digit 1 appearing in all non-negative integer...
摘要:但是,往往會有可以優化的空間。假設我們用來記錄子數組之間,第一個取數字的玩家和第二個取數字的玩家之間最大的差距。再考慮初始情況,即當數組長度為時,可以得知此時玩家一和玩家二之間的差距即為該數組元素的值。 題目要求 Given an array of scores that are non-negative integers. Player 1 picks one of the numb...
摘要:不過這里有個小技巧,因為我們只要加,所以不用完全模擬加法的所有規則一個數如果不是,那加以后不會對其他位產生影響。 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...
閱讀 423·2019-08-29 12:44
閱讀 3001·2019-08-26 17:49
閱讀 2398·2019-08-26 13:40
閱讀 1180·2019-08-26 13:39
閱讀 3656·2019-08-26 11:59
閱讀 1814·2019-08-26 10:59
閱讀 2454·2019-08-23 18:33
閱讀 2687·2019-08-23 18:30