我可太喜歡這個(gè)題了

今天我們來看一道賊棒的題目，題目不長(zhǎng)，很經(jīng)典，也很容易理解，我們一起來看一哈吧，

大家也可能做過這道題，那就再復(fù)習(xí)一下唄，如果沒做過的話，可以看完文章，自己去 AC 一下，不過寫代碼的時(shí)候，要自己完全寫出來，這樣才能有收獲，下面我們看題目吧。

leetcode 233. 數(shù)字 1 的個(gè)數(shù)

題目描述

給定一個(gè)整數(shù) n，計(jì)算所有小于等于 n 的非負(fù)整數(shù)中數(shù)字 1 出現(xiàn)的個(gè)數(shù)。

示例 1：

輸入：n = 13 輸出：6

示例 2：

輸入：n = 0 輸出：0

太喜歡這種簡(jiǎn)潔的題目啦，言簡(jiǎn)意賅，就是讓咱們找出小于等于 n 的非負(fù)整數(shù)中數(shù)字 1 出現(xiàn)的個(gè)數(shù)。

大家看到這個(gè)題目的第一印象，可能會(huì)這樣想，哦，讓我們求 1 的個(gè)數(shù)。

吶我們直接逐位遍歷每個(gè)數(shù)的每一位，當(dāng)遇到 1 的時(shí)候，計(jì)數(shù)器 +1，不就行了。

嗯，很棒的方法，可惜會(huì)超時(shí)。

或者說，我們可以先將所有數(shù)字拼接起來，然后再逐位遍歷，這樣仍會(huì)超時(shí)。

大家再思考一下還有沒有別的方法呢？

既然題目讓我們統(tǒng)計(jì)小于等于 n 的非負(fù)整數(shù)中數(shù)字 1 出現(xiàn)的個(gè)數(shù)。

那我們可以不可這樣統(tǒng)計(jì)。

我們假設(shè) n = abcd，某個(gè)四位數(shù)。

那我們完全可以統(tǒng)計(jì)每一位上 1 出現(xiàn)的次數(shù)，個(gè)數(shù)上 1 出現(xiàn)的次數(shù)，十位上 1 出現(xiàn)的次數(shù)，百位 ，千位......

也就是說小于等于 n 的所有數(shù)字中，個(gè)位上出現(xiàn) 1 的次數(shù) + 十位出現(xiàn) 1 的次數(shù) + ...... 最后得到的就是總的出現(xiàn)次數(shù)。

見下圖

我們假設(shè) n = ?13 (用個(gè)小點(diǎn)的數(shù)，比較容易舉例)

我們需要統(tǒng)計(jì)小于等于 13 的數(shù)中，出現(xiàn) 1 的次數(shù)，

通過上圖可知，個(gè)位上 1 出現(xiàn) 2 次，十位上 1 出現(xiàn) 4 次

那么總次數(shù)為 2 + 4 = 6 次。

另外我們發(fā)現(xiàn) 11 這個(gè)數(shù)，會(huì)被統(tǒng)計(jì) 2 次，它的十位和個(gè)位都為 1?

我們這個(gè)題目是要統(tǒng)計(jì) 1 出現(xiàn)的次數(shù)，而不是統(tǒng)計(jì)包含 1 的整數(shù)，所以上訴方法不會(huì)出現(xiàn)重復(fù)統(tǒng)計(jì)的情況。

我們題目已經(jīng)有大概思路啦，下面的難點(diǎn)就是如何統(tǒng)計(jì)每一位中 1 出現(xiàn)的次數(shù)呢？

我們完全可以通過遍歷 n 的每一位來得到總個(gè)數(shù)，見下圖

假設(shè)我們想要得到十位上 1 出現(xiàn)的次數(shù)，當(dāng)前我們指針指向十位，

我們稱之為當(dāng)前位。num 則代表當(dāng)前位的位因子，當(dāng)前位為個(gè)位時(shí) num = 1，十位時(shí)為 10，百位時(shí)為 100....

那我們將當(dāng)前位左邊的定義為高位，當(dāng)前位右邊的定義位低位。

例：n = 1004 ，此時(shí)指針指向十位（當(dāng)前位）num = 10，高位為百位，千位，低位為個(gè)位

而且我們發(fā)現(xiàn)數(shù)字的某一位的取值范圍為 0 ~ 9 ,那么我們可以將這 10 個(gè)數(shù)分為 3 類，小于 1 （當(dāng)前位數(shù)字為 0 ），等于 1（當(dāng)前位數(shù)字為 1 ） ，大于 1（當(dāng)前位上數(shù)字為 2 ~ 9），下面我們就來分別考慮三種情況。

我們進(jìn)行舉例的 n 為 1004，1014，1024。重點(diǎn)討論十位上 3 種不同情況。

大家閱讀下方文字之前，先想象自己腦子里有一個(gè)行李箱的滾輪密碼鎖，我們固定其中的某一位，然后可以隨意滑動(dòng)其他位，這樣可以幫助大家理解。

注：該比喻來自與網(wǎng)友 ryan0414，看到的時(shí)候，不禁驚呼可太貼切了！

n = 1004

我們想要計(jì)算出小于等于 1004 的非負(fù)整數(shù)中，十位上出現(xiàn) 1 的次數(shù)。

也就是當(dāng)前位為十位，數(shù)字為 0 時(shí)，十位上出現(xiàn) 1 的次數(shù)。

解析：為什么我們可以直接通過高位數(shù)字 * num，得到 1 出現(xiàn)的次數(shù)

因?yàn)槲覀兏呶粸?10，可變范圍為 0 ~ 10，但是我們的十位為 0 ，所以高位為 10 的情況取不到，所以共有 10 種情況。

又當(dāng)前位為十位，低位共有 1 位，可選范圍為 0 ~ 9 共有 10 種情況，所以直接可以通過 10 * 10 得到。

其實(shí)不難理解，我們可以設(shè)想成行李箱的密碼盤，在一定范圍內(nèi)，也就是上面的 0010 ~ 0919 ?， 固定住一位為 1 ，只能移動(dòng)其他位，看共有多少種組合。

好啦，這個(gè)情況我們已經(jīng)搞明白啦，下面我們看另一種情況。

n = 1014

我們想要計(jì)算出小于等于 1014 的非負(fù)整數(shù)中，十位上出現(xiàn) 1 的次數(shù)。

也就是當(dāng)前位為十位，數(shù)字為 1 時(shí)，十位上出現(xiàn) 1 的次數(shù)。

我們?cè)谛∮?1014 的非負(fù)整數(shù)中，十位上為 1 的最小數(shù)字為 10，最大數(shù)字為 1014，所以我們需要在 ?10 ~ 1014 這個(gè)范圍內(nèi)固定住十位上的 1 ，移動(dòng)其他位。

其實(shí)然后我們可以將 1014 看成是 1004 + 10 = 1014

則可以將 10 ~ 1014 ?拆分為兩部分 0010 ~ 0919 （小于 1004 ），1010 ~ 1014。

見下圖

解析：為什么我們可以直接通過 高位數(shù)字 * num + 低位數(shù)字 + 1 ?即 10 * 10 + 4 + 1

得到 1 出現(xiàn)的次數(shù)

高位數(shù)字 * num 是得到第一段的次數(shù)，第二段為 低位數(shù)字 + 1，求第二段時(shí)我們高位數(shù)字和當(dāng)前位已經(jīng)固定，

我們可以改變的只有低位。

可以繼續(xù)想到密碼盤，求第二段時(shí)，把前 3 位固定，只能改變最后一位。最后一位最大能到 4 ，那么共有幾種情況？

n = 1024

我們想要計(jì)算出小于等于 1024 的非負(fù)整數(shù)中，十位上出現(xiàn) 1 的次數(shù)。

也就是當(dāng)前位為十位，數(shù)字為 2 ~ 9 時(shí)，十位上出現(xiàn) 1 的次數(shù)。其中最小的為 0010，最大的為 1019

我們也可以將其拆成兩段 0010 ~ 0919，1010 ~ 1019

解析：為什么我們可以直接通過高位數(shù)字 * num + num， 10 * 10 + 10 得到 1 出現(xiàn)的次數(shù)

第一段和之前所說一樣，第二段的次數(shù)，我們此時(shí)已經(jīng)固定了高位和當(dāng)前位，當(dāng)前位為 1，低位可以隨意取值，上訴例子中，當(dāng)前位為 10，低位為位數(shù)為 1，則可以取值 0 ~ 9 的任何數(shù)，則共有 10 (num) 種可能。

好啦，這個(gè)題目大家應(yīng)該理解的差不多啦，

下面我們通過動(dòng)畫模擬一下，是怎樣一步一步的計(jì)算出，小于等于 1014 的數(shù)中 1 出現(xiàn)的次數(shù)。

注：藍(lán)色高位，橙色當(dāng)前位，綠色低位

初始化：low = 0， cur = 0, ?num = 1, ?count = 0, ? high = n ;

好啦，下面我們看一下題目代碼吧

注：下方代碼沒有簡(jiǎn)寫，也都標(biāo)有注釋，大家可以結(jié)合動(dòng)畫邊思考邊閱讀。

題目代碼

class?Solution?{
????public?int?countDigitOne(int?n)?{
????????//高位
????????int?high?=?n;
????????//低位
????????int?low?=?0;
????????//當(dāng)前位
????????int?cur?=?0;
????????int?count?=?0;
????????int?num?=?1;
????????while?(high?!=?0)?{
????????????cur?=?high?%?10;
????????????high?/=?10;
????????????//這里我們可以提出?high?*?num?因?yàn)槲覀儼l(fā)現(xiàn)無論為幾，都含有它?
????????????if?(cur?==?0)?count?+=?high?*?num;
????????????else?if?(cur?==?1)?count?+=?high?*?num?+?1?+?low;?
????????????else?count?+=?(high?+?1)?*?num;
????????????//低位
????????????low?=?cur?*?num?+?low;??????????????????
????????????num?*=?10;
????????}
????????return?count;
????}
}

時(shí)間復(fù)雜度：循環(huán)次數(shù)為數(shù)字 n 的位數(shù)，則為 O(logn)

空間復(fù)雜度：O(1)

推薦閱讀

• 《劍指offer》

• ? Krahets, K 神解析

好啦，今天就到這吧，拜了個(gè)拜，需要一起刷題的同學(xué)，可以在小屋內(nèi)點(diǎn)擊刷題小隊(duì)。