算法作業(yè)有一個(gè)小的題目：
一本書的頁(yè)碼從自然數(shù)1開始編碼直到自然數(shù)n哨查，按照通常的習(xí)慣，每個(gè)頁(yè)碼都不包含多余的前導(dǎo)數(shù)字0剧辐，例如第6頁(yè)用數(shù)字6而不是06或者006表示『ィ現(xiàn)在給定表示書的總頁(yè)碼的十進(jìn)制整數(shù)n(1 =< n <= 10^9)，編程計(jì)算書的全部頁(yè)碼中分別用到多少次數(shù)字0, 1, 2, 3, 4, 5, 6, 7, 8, 9荧关。
比如一本數(shù)有123頁(yè)溉奕，那么各數(shù)字出現(xiàn)次數(shù)如下圖：
解題思路不是很難想到，但是在寫作業(yè)報(bào)告忍啤，發(fā)現(xiàn)很難清楚地把這個(gè)算法過程給寫出來加勤。于是就認(rèn)真組織了語言，配上幾幅圖片同波，希望能把算法講明白鳄梅。（好多內(nèi)容自己會(huì)但不一定講的明白，講的明白也不一定寫的明白）
思路
對(duì)于任意的一個(gè)頁(yè)碼數(shù)未檩，將其分為兩部分：個(gè)位數(shù)部分?jǐn)?shù)字和其他部分?jǐn)?shù)字戴尸。那么對(duì)于總頁(yè)碼為N的書本，其所有的頁(yè)碼可以放在如下的一個(gè)表格中冤狡，綠色表格代表頁(yè)碼孙蒙，里面的任意數(shù)字X[i][j] = i * 10 + j(方便我們理解项棠，這里假設(shè)N-3==0)：
現(xiàn)在要做的就是統(tǒng)計(jì)所有綠色表格中數(shù)字0到9出現(xiàn)的次數(shù)，綠色表格（也即任意一個(gè)頁(yè)碼）中數(shù)字組成其實(shí)可以拆分為對(duì)應(yīng)的行和列的數(shù)字組成马篮。例如對(duì)于頁(yè)碼123沾乘，其中1、2浑测、3各出現(xiàn)1次翅阵，它對(duì)應(yīng)的行的是123/10=12，列為123%10=3迁央，12和3中1掷匠、2、3也是各出現(xiàn)一次岖圈。
要計(jì)算所有的頁(yè)碼中0到9出現(xiàn)的總次數(shù)讹语，可以轉(zhuǎn)換為所有行中0到9出現(xiàn)的次數(shù)和所有列中0到9出現(xiàn)的次數(shù)。對(duì)于每一個(gè)綠色表格蜂科，其對(duì)應(yīng)的行和列中數(shù)字各出現(xiàn)一次顽决。因此我們可以先統(tǒng)計(jì)每一行和每一列綠色方格的數(shù)目，然后就可以得出每一行和每一列中0數(shù)字出現(xiàn)的次數(shù)导匣。如下圖：
- 行的計(jì)數(shù)：注意由于頁(yè)碼沒有01頁(yè)才菠、02頁(yè)這一說法，所以行[0]中0出現(xiàn)0次贡定，行[1]中1出現(xiàn)10次赋访，行[2]中2出現(xiàn)10次...行[11]中11出現(xiàn)10次...；
- 列的計(jì)數(shù)：列[0]中0出現(xiàn)N/10次缓待，列[1]中1出現(xiàn)N/10+1次...列[9]中9出現(xiàn)N/10次蚓耽。
看上去每行每列數(shù)字出現(xiàn)的次數(shù)有點(diǎn)凌亂，其實(shí)稍微劃分一下組成部分就可以了旋炒，如下分為五部分來計(jì)算（這里假設(shè)N-3==0步悠，方便我們講解）：
- 第一部分：第一行[0]中各列數(shù)字均出現(xiàn)1次；
- 第二部分：最后一行[N/10]中列[0]瘫镇、列[1]贤徒、列[2]、列[3]中數(shù)字0汇四、1接奈、2、3各出現(xiàn)1次通孽；
- 第三部分：列[0]到列[9]中0序宦、1、2...9每個(gè)數(shù)字都出現(xiàn)N/10 - 1次背苦。
- 第四部分：行[1]到行[N/10-1]中每個(gè)數(shù)字出現(xiàn)的次數(shù)（也就是總頁(yè)碼為N/10 - 1時(shí)各個(gè)數(shù)字出現(xiàn)的次數(shù)--這里要遞歸哦）乘以10互捌。
- 第五部分：行[N/10]中每個(gè)數(shù)字均出現(xiàn)4次潘明。
實(shí)現(xiàn)
Python實(shí)現(xiàn)如下：
def count_num(num):
nums = [0 for x in range(10)]
if num < 10:
for i in range(1, num + 1):
nums[i] = 1
return nums
# Part 1
for i in range(1, 10):
nums[i] += 1
# Part 2
units = num % 10
for i in range(0, units + 1):
nums[i] += 1
# Part 3
others = num / 10 - 1
for i in range(0, 10):
nums[i] += others
# Part4
count_others = count_num(others)
for i in range(10):
times_i = count_others[i] * 10
nums[i] += times_i
# Part 5
digit_keep = []
while num > 0:
digit_keep.append(num % 10)
num = num / 10
times_units = digit_keep[0] + 1
for digit in digit_keep[1:]:
nums[digit] += times_units
return nums
這篇文章沒有什么技術(shù)干貨，純粹逼自己試著去把一些算法寫的明白秕噪，大家覺得哪塊講的不明白钳降，我可以持續(xù)改進(jìn)哈。
更多文章腌巾，請(qǐng)移步我的博客
