資訊專欄INFORMATION COLUMN
摘要：好多內(nèi)容自己會但不一定講的明白，講的明白也不一定寫的明白思路對于任意的一個頁碼數(shù)，將其分為兩部分個位數(shù)部分數(shù)字和其他部分數(shù)字。
算法作業(yè)有一個小的題目：
一本書的頁碼從自然數(shù)1開始編碼直到自然數(shù)n，按照通常的習慣，每個頁碼都不包含多余的前導數(shù)字0，例如第6頁用數(shù)字6而不是06或者006表示?，F(xiàn)在給定表示書的總頁碼的十進制整數(shù)n(1 =< n <= 10^9)，編程計算書的全部頁碼中分別用到多少次數(shù)字0, 1, 2, 3, 4, 5, 6, 7, 8, 9。
比如一本數(shù)有123頁，那么各數(shù)字出現(xiàn)次數(shù)如下圖：
解題思路不是很難想到，但是在寫作業(yè)報告，發(fā)現(xiàn)很難清楚地把這個算法過程給寫出來。于是就認真組織了語言，配上幾幅圖片，希望能把算法講明白。（好多內(nèi)容自己會但不一定講的明白，講的明白也不一定寫的明白）
思路對于任意的一個頁碼數(shù)，將其分為兩部分：個位數(shù)部分數(shù)字和其他部分數(shù)字。那么對于總頁碼為N的書本，其所有的頁碼可以放在如下的一個表格中，綠色表格代表頁碼，里面的任意數(shù)字Xi = i * 10 + j(方便我們理解，這里假設N-3==0)：
現(xiàn)在要做的就是統(tǒng)計所有綠色表格中數(shù)字0到9出現(xiàn)的次數(shù)，綠色表格（也即任意一個頁碼）中數(shù)字組成其實可以拆分為對應的行和列的數(shù)字組成。例如對于頁碼123，其中1、2、3各出現(xiàn)1次，它對應的行的是123/10=12，列為123%10=3，12和3中1、2、3也是各出現(xiàn)一次。
要計算所有的頁碼中0到9出現(xiàn)的總次數(shù)，可以轉(zhuǎn)換為所有行中0到9出現(xiàn)的次數(shù)和所有列中0到9出現(xiàn)的次數(shù)。對于每一個綠色表格，其對應的行和列中數(shù)字各出現(xiàn)一次。因此我們可以先統(tǒng)計每一行和每一列綠色方格的數(shù)目，然后就可以得出每一行和每一列中0數(shù)字出現(xiàn)的次數(shù)。如下圖：
行的計數(shù)：注意由于頁碼沒有01頁、02頁這一說法，所以行[0]中0出現(xiàn)0次，行[1]中1出現(xiàn)10次，行[2]中2出現(xiàn)10次...行[11]中11出現(xiàn)10次...；
列的計數(shù)：列[0]中0出現(xiàn)N/10次，列[1]中1出現(xiàn)N/10+1次...列[9]中9出現(xiàn)N/10次。
看上去每行每列數(shù)字出現(xiàn)的次數(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每個數(shù)字都出現(xiàn)N/10 - 1次。
第四部分：行[1]到行[N/10-1]中每個數(shù)字出現(xiàn)的次數(shù)（也就是總頁碼為N/10 - 1時各個數(shù)字出現(xiàn)的次數(shù)--這里要遞歸哦）乘以10。
第五部分：行[N/10]中每個數(shù)字均出現(xiàn)4次。
實現(xiàn)Python實現(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ù)改進哈。
可以去我的主頁看更多的博客。
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/37609.html
摘要：前言今天和大家一起聊聊的推薦書籍，每一本都是精選，做前端開發(fā)的朋友們?nèi)绻麤]讀過，可以嘗試一下。如果怕麻煩，也可以關(guān)注曉舟報告，發(fā)送獲取書籍，四個字，就可以得到電子書的提取碼。 前言 今天和大家一起聊聊JavaScript的推薦書籍，每一本都是精選，做前端開發(fā)的朋友們?nèi)绻麤]讀過，可以嘗試一下。下面給大家簡單介紹了書的內(nèi)容，還有讀書的方法，希望可以幫大家提升讀書效率。 一、《JavaScr...
摘要：下面這張解決了怎么用完成任務的問題，最后，開發(fā)者怕你懷疑的強大，又提供了幾個和許多成功的案例來打消我們的顧慮。拿下助攻決定用之后，就開始補充相應的知識啦。來欣賞一下一些應用的截圖吧，不得不說開發(fā)出的應用一點不比原生的丑陋啊。 博客地址 每個程序員都希望用自己喜歡的語言，自己喜歡的平臺、工具，寫自己喜歡的程序。于是我們會看到有人在Win下用Visual Studio愉快地coding，也...
摘要：下載器下載器負責獲取頁面數(shù)據(jù)并提供給引擎，而后提供給。下載器中間件下載器中間件是在引擎及下載器之間的特定鉤子，處理傳遞給引擎的。一旦頁面下載完畢，下載器生成一個該頁面的，并將其通過下載中間件返回方向發(fā)送給引擎。 作者：xiaoyu微信公眾號：Python數(shù)據(jù)科學知乎：Python數(shù)據(jù)分析師 在爬蟲的路上，學習scrapy是一個必不可少的環(huán)節(jié)。也許有好多朋友此時此刻也正在接觸并學習sc...
摘要：大會年，我去了。小會值得一提的是，今年月份，我參加了一個的分享會。出游沙巴這是部門組織的出游，獲得了最佳團隊，拿到了一筆經(jīng)費，于是有了這次出游。于是，我的下個目的地是西藏。 轉(zhuǎn)眼間 2017 年過去了。我已經(jīng)不能說自己是去年的畢業(yè)生了，時光匆匆，感覺自己越來越老了。 這一年，我所經(jīng)歷的，讓我收獲很多，讓我懂得很多，讓我明白了很多。也許是明確了某一個目標，也許是其它的什么，我覺得，201...
摘要：菜鳥教程這是一個屬性其值是字符串菜鳥教程同上這是一個屬性其值是字符串用于定義的函數(shù)，可以通過來返回函數(shù)值。它們都有前綴，以便與用戶定義的屬性區(qū)分開來。 開篇語 我最近學習了js,取得進步,現(xiàn)在學習vue.js.建議新手學習,請不要用npm的方式(vue-cli,vue腳手架),太復雜了. 請直接下載vue.js文件本地引入,就上手學習吧參照菜鳥教程網(wǎng)站的vue.js教程http://...
閱讀 3425·2021-09-22 16:00
閱讀 3468·2021-09-07 10:26
閱讀 3029·2019-08-30 15:55
閱讀 2869·2019-08-30 13:48
閱讀 1376·2019-08-30 12:58
閱讀 2178·2019-08-30 11:15
閱讀 958·2019-08-30 11:08
閱讀 534·2019-08-29 18:41
