資訊專欄INFORMATION COLUMN
摘要：遞歸復(fù)雜度思路每次將一個數(shù)拆分成兩部分考慮，并考慮當前最高是不是比如，將數(shù)拆分成，和，這兩部分分別計算。每次抹去高位，觀察重復(fù)情況。代碼代表位數(shù)，代表最高的值除了高位的剩余部分
LeetCode[23] Number of Digit One
遞歸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.
復(fù)雜度
O(N), ? O(1)
思路
每次將一個數(shù)拆分成兩部分考慮，并考慮當前最高是不是1.
比如115，將數(shù)拆分成，15和0-100，這兩部分分別計算。
如果最高位是1的數(shù)，那么一定會包括 100-115這16個數(shù)，除了那兩部分之外。
每次抹去高位，觀察重復(fù)情況。
代碼
public int countDigitOne(int n) {
if(n < 10) {
return n > 0 ? 1 : 0;
}
// count代表位數(shù)，num代表最高的值
int level = 10, num = 0;
int count = 0;
// integer overflow;
while(n / level >= 10) {
level *= 10;
}
num = n / level;
//
if(num == 1) {
count += (n - level + 1) + countDigitOne(level - 1);
}
else if(num > 1) {
count += num * countDigitOne(level - 1) + level;
}
// 除了高位的剩余部分；
count += countDigitOne(n - level * num);
return count;
//return level;
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/65210.html
摘要：題目給一個數(shù)求從到所有數(shù)中數(shù)字在各個位上出現(xiàn)的總次數(shù)。解法可以做循環(huán)從到挨個找。更好的是用歸納法總結(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ù)中數(shù)字的個數(shù)。比如比小的正整數(shù)中包含的有，一共有個。因此，我們需要用更好的方法，減少這種方法的浪費。其實等價于中的的個數(shù)。 題目要求 Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal...
摘要：只有大于左邊界才部分包含，且只有大于右邊界的數(shù)才完整包含，這些中多余的。對于而言，部分包含用余數(shù)做，完整包含用進位后的商做。逐位向上累加，可得結(jié)果。千位萬位，大致如此。例如個位十位百位千位 Problem Given an integer n, count the total number of digit 1 appearing in all non-negative integer...
摘要：但是，往往會有可以優(yōu)化的空間。假設(shè)我們用來記錄子數(shù)組之間，第一個取數(shù)字的玩家和第二個取數(shù)字的玩家之間最大的差距。再考慮初始情況，即當數(shù)組長度為時，可以得知此時玩家一和玩家二之間的差距即為該數(shù)組元素的值。 題目要求 Given an array of scores that are non-negative integers. Player 1 picks one of the numb...
摘要：不過這里有個小技巧，因為我們只要加，所以不用完全模擬加法的所有規(guī)則一個數(shù)如果不是，那加以后不會對其他位產(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...
閱讀 1090·2021-11-22 15:33
閱讀 3395·2021-11-08 13:20
閱讀 1414·2021-09-22 10:55
閱讀 2075·2019-08-29 11:08
閱讀 800·2019-08-26 12:24
閱讀 3101·2019-08-23 17:15
閱讀 2260·2019-08-23 16:12
閱讀 1971·2019-08-23 16:09
