資訊專(zhuān)欄INFORMATION COLUMN
摘要：遞歸復(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 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)
思路
每次將一個(gè)數(shù)拆分成兩部分考慮，并考慮當(dāng)前最高是不是1.
比如115，將數(shù)拆分成，15和0-100，這兩部分分別計(jì)算。
如果最高位是1的數(shù)，那么一定會(huì)包括 100-115這16個(gè)數(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)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://m.specialneedsforspecialkids.com/yun/65210.html
摘要：題目給一個(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:...
摘要：題目要求計(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...
摘要：只有大于左邊界才部分包含，且只有大于右邊界的數(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)槲覀冎灰樱圆挥猛耆M加法的所有規(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...
閱讀 1062·2021-11-22 15:33
閱讀 3374·2021-11-08 13:20
閱讀 1390·2021-09-22 10:55
閱讀 2059·2019-08-29 11:08
閱讀 782·2019-08-26 12:24
閱讀 3078·2019-08-23 17:15
閱讀 2240·2019-08-23 16:12
閱讀 1944·2019-08-23 16:09
