我可太喜歡這個題了

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

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

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

題目描述

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

示例 1：

輸入：n = 13 輸出：6

示例 2：

輸入：n = 0 輸出：0

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

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

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

嗯，很棒的方法，可惜會超時。

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

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

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

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

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

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

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

見下圖

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

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

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

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

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

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

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

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

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

我們稱之為當前位。num 則代表當前位的位因子，當前位為個位時 num = 1，十位時為 10，百位時為 100....

那我們將當前位左邊的定義為高位，當前位右邊的定義位低位。

例：n = 1004 ，此時指針指向十位（當前位）num = 10，高位為百位，千位，低位為個位

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

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

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

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

n = 1004

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

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

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

因為我們高位為 10，可變范圍為 0 ~ 10，但是我們的十位為 0 ，所以高位為 10 的情況取不到，所以共有 10 種情況。

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

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

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

n = 1014

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

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

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

其實然后我們可以將 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ù)字和當前位已經(jīng)固定，

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

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

n = 1024

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

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

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

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

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

好啦，這個題目大家應該理解的差不多啦，

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

注：藍色高位，橙色當前位，綠色低位

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

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

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

題目代碼

class?Solution?{

public?int?countDigitOne(int?n)?{

//高位

int?high?=?n;

//低位

int?low?=?0;

//當前位

int?cur?=?0;

int?count?=?0;

int?num?=?1;

while?(high?!=?0)?{

cur?=?high?%?10;

high?/=?10;

//這里我們可以提出?high?*?num?因為我們發(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;

}

}

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

空間復雜度：O(1)

推薦閱讀

《劍指offer》

Krahets, K 神解析

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

數(shù)據(jù)結(jié)構(gòu)

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔相應法律責任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實的內(nèi)容，請聯(lián)系我們jiasou666@gmail.com 處理，核實后本網(wǎng)站將在24小時內(nèi)刪除侵權(quán)內(nèi)容。

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔相應法律責任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實的內(nèi)容，請聯(lián)系我們jiasou666@gmail.com 處理，核實后本網(wǎng)站將在24小時內(nèi)刪除侵權(quán)內(nèi)容。