資訊專(zhuān)欄INFORMATION COLUMN
摘要：題目給一個(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:
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.
給一個(gè)數(shù)n,求從1到n所有數(shù)中數(shù)字1在各個(gè)位上出現(xiàn)的總次數(shù)。
解法：
可以做循環(huán)從1到n挨個(gè)找。慢。
更好的是用歸納法總結(jié)出1出現(xiàn)的次數(shù)的規(guī)律。
假設(shè)n=abcde五位數(shù)字的時(shí)候，我們分析百位c，有三種情況：
1）c == 0的時(shí)候，比如12013，此時(shí)百位出現(xiàn)1的是：00 100 ~ 00 199， 01 100~01 199，……，11 100~ 11 199，共1200個(gè)，顯然這個(gè)有高位數(shù)字決定，并且受當(dāng)前位數(shù)影響； 個(gè)數(shù)就是 ab*100
2）c == 1的時(shí)候，比如12113，此時(shí)百位出現(xiàn)1的肯定包括c=0的情況，另外還需要考慮低位的情況即：00100 ~ 00113共14個(gè); 個(gè)數(shù)等于ab*100+ de + 1
3）c >= 2的時(shí)候，比如12213，此時(shí)百位出現(xiàn)1的是：00 100 ~ 00 199， 01 100~01 199，……，11 100~ 11 199，12 100 ~ 12 199，共1300個(gè)，這個(gè)有高位數(shù)字決定，其實(shí)是加一，并且乘以當(dāng)前位數(shù); 個(gè)數(shù)就是 (ab+1)*100
總結(jié)起來(lái)，對(duì)于一個(gè) n = abcde 來(lái)說(shuō)，百位出現(xiàn)1的個(gè)數(shù)計(jì)算方法為 ：
if(c==0) ans = ab*100;
if(c==1) ans = ab*100+cd+1
if(c>1) ans = (ab+1)*100
代碼：
public class Solution {
public int countDigitOne(int n) {
if(n <= 0) return 0;
int q = n; int x = 1; int ans = 0; int temp = 0;
do{
temp = q%10;
q/=10;
if(temp == 0) ans+=q*x;
else if(temp == 1) ans+=q*x + n%x + 1;
else
ans+=(q+1)*x;
x*=10;
} while (q > 0);
return ans;
}
}
Ref：
java one pass easy understand
leetcode 233
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/66097.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...
摘要：題目要求計(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...
摘要：加一給定一個(gè)由整數(shù)組成的非空數(shù)組所表示的非負(fù)整數(shù)，在該數(shù)的基礎(chǔ)上加一。示例輸入輸出解釋輸入數(shù)組表示數(shù)字。思路指針從最后往前移動(dòng)，若值為逐個(gè)加一，并賦值。不等于則退出循環(huán)。首位如果為是則證明需要進(jìn)一。只需首位賦值即可。 加一 給定一個(gè)由整數(shù)組成的非空數(shù)組所表示的非負(fù)整數(shù)，在該數(shù)的基礎(chǔ)上加一。 最高位數(shù)字存放在數(shù)組的首位， 數(shù)組中每個(gè)元素只存儲(chǔ)一個(gè)數(shù)字。 你可以假設(shè)除了整數(shù) 0 之外，這個(gè)...
摘要：加一給定一個(gè)由整數(shù)組成的非空數(shù)組所表示的非負(fù)整數(shù)，在該數(shù)的基礎(chǔ)上加一。示例輸入輸出解釋輸入數(shù)組表示數(shù)字。思路指針從最后往前移動(dòng)，若值為逐個(gè)加一，并賦值。不等于則退出循環(huán)。首位如果為是則證明需要進(jìn)一。只需首位賦值即可。 加一 給定一個(gè)由整數(shù)組成的非空數(shù)組所表示的非負(fù)整數(shù)，在該數(shù)的基礎(chǔ)上加一。 最高位數(shù)字存放在數(shù)組的首位， 數(shù)組中每個(gè)元素只存儲(chǔ)一個(gè)數(shù)字。 你可以假設(shè)除了整數(shù) 0 之外，這個(gè)...
閱讀 4718·2021-09-10 11:22
閱讀 601·2019-08-30 11:17
閱讀 2624·2019-08-30 11:03
閱讀 481·2019-08-29 11:18
閱讀 3523·2019-08-28 17:59
閱讀 3274·2019-08-26 13:40
閱讀 3254·2019-08-26 10:29
閱讀 1204·2019-08-26 10:14
