Leetcode-233-Number of Digit One

數(shù)數(shù)字的題目說難也難籽腕，說簡單也簡單，難就難在不重不漏纸俭，簡單就簡單在方法找對了皇耗，就是一個(gè)公式的事兒。

這道題的思路其實(shí)不難找揍很，我們考慮一下什么時(shí)候會(huì)出現(xiàn)數(shù)字1：

1郎楼、11、21窒悔、……呜袁、91
10、11简珠、12阶界、……、19
100聋庵、101膘融、……、199

我們看到祭玉，統(tǒng)計(jì)1在各個(gè)數(shù)位上出現(xiàn)的次數(shù)比較簡單氧映，不會(huì)重復(fù)也不易遺漏。我們看到11在這里出現(xiàn)了兩次脱货，按照數(shù)位計(jì)算的話就是十位計(jì)算一次個(gè)位計(jì)算一次岛都，并不會(huì)產(chǎn)生重復(fù)。

現(xiàn)在的問題就是蹭劈，如何計(jì)算各個(gè)數(shù)位上1的個(gè)數(shù)疗绣。

比如我們看數(shù)字 $142857$ ，個(gè)位上有多少個(gè) $1$ 呢铺韧？把 $142857$ 分成 $14285$ 和 $7$ 兩部分多矮，可以看到，前一部分可以取 $00000\sim14285$ ，后一部分可以取 $1(<7)$ 塔逃，于是個(gè)位上 $1$ 的個(gè)數(shù)就是 $14285+1=14286$ 讯壶。

下面我們看十位，同樣的思路湾盗，我們把 $142857$ 分成 $1428$ 和 $57$ 兩部分伏蚊，前一部分可以取 $0000\sim1428$ ，后一部分可以取 $10\sim19(<57)$ 于是十位上是 $1$ 的個(gè)數(shù)為 $(1428+1)\times 10=14290$ 格粪。

依次進(jìn)行下去并將結(jié)果相加即為最終結(jié)果躏吊。

需要注意的特殊情況是某一位上的數(shù)字為 $0$ 和 $1$ 的情況，比如 $142807$ 帐萎，我們在考查十位上數(shù)字 $1$ 的個(gè)數(shù)的時(shí)候應(yīng)該取 $1428$ (而非 $1429$ ) $\times10$ 比伏，因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=07%3C10" alt="07<10" mathimg="1">。

當(dāng)數(shù)字為 $142817$ 疆导，十位上數(shù)字 $1$ 的個(gè)數(shù)為 $1428\times10+(17\% 10+1)$ 赁项。

從而我們可以由以上規(guī)律得到一個(gè)統(tǒng)一的計(jì)算公式，代碼如下：

class Solution {
public:
    int countDigitOne(int n) 
    {
        int res = 0;
        for (long i=1;i<=n;i*=10) 
            res+=(n/i+8)/10*i+(n/i%10==1)*(n%i+1);
        return res;
    }
};

最后編輯于：2019.05.30 22:46:54

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者