講的明白，但寫的明白嗎？

Alliot 發布于2019-07-24 18:08 / 1353人閱讀

摘要：好多內容自己會但不一定講的明白，講的明白也不一定寫的明白思路對于任意的一個頁碼數，將其分為兩部分個位數部分數字和其他部分數字。

算法作業有一個小的題目：

一本書的頁碼從自然數1開始編碼直到自然數n，按照通常的習慣，每個頁碼都不包含多余的前導數字0，例如第6頁用數字6而不是06或者006表示。現在給定表示書的總頁碼的十進制整數n(1 =< n <= 10^9)，編程計算書的全部頁碼中分別用到多少次數字0, 1, 2, 3, 4, 5, 6, 7, 8, 9。

比如一本數有123頁，那么各數字出現次數如下圖：

解題思路不是很難想到，但是在寫作業報告，發現很難清楚地把這個算法過程給寫出來。于是就認真組織了語言，配上幾幅圖片，希望能把算法講明白。（好多內容自己會但不一定講的明白，講的明白也不一定寫的明白）

思路

對于任意的一個頁碼數，將其分為兩部分：個位數部分數字和其他部分數字。那么對于總頁碼為N的書本，其所有的頁碼可以放在如下的一個表格中，綠色表格代表頁碼，里面的任意數字Xi = i * 10 + j(方便我們理解，這里假設N-3==0)：

現在要做的就是統計所有綠色表格中數字0到9出現的次數，綠色表格（也即任意一個頁碼）中數字組成其實可以拆分為對應的行和列的數字組成。例如對于頁碼123，其中1、2、3各出現1次，它對應的行的是123/10=12，列為123%10=3，12和3中1、2、3也是各出現一次。

要計算所有的頁碼中0到9出現的總次數，可以轉換為所有行中0到9出現的次數和所有列中0到9出現的次數。對于每一個綠色表格，其對應的行和列中數字各出現一次。因此我們可以先統計每一行和每一列綠色方格的數目，然后就可以得出每一行和每一列中0數字出現的次數。如下圖：

行的計數：注意由于頁碼沒有01頁、02頁這一說法，所以行[0]中0出現0次，行[1]中1出現10次，行[2]中2出現10次...行[11]中11出現10次...；

列的計數：列[0]中0出現N/10次，列[1]中1出現N/10+1次...列[9]中9出現N/10次。

看上去每行每列數字出現的次數有點凌亂，其實稍微劃分一下組成部分就可以了，如下分為五部分來計算（這里假設N-3==0，方便我們講解）：

第一部分：第一行[0]中各列數字均出現1次；

第二部分：最后一行[N/10]中列[0]、列[1]、列[2]、列[3]中數字0、1、2、3各出現1次；

第三部分：列[0]到列[9]中0、1、2...9每個數字都出現N/10 - 1次。

第四部分：行[1]到行[N/10-1]中每個數字出現的次數（也就是總頁碼為N/10 - 1時各個數字出現的次數--這里要遞歸哦）乘以10。

第五部分：行[N/10]中每個數字均出現4次。

實現

Python實現如下：

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

這篇文章沒有什么技術干貨，純粹逼自己試著去把一些算法寫的明白，大家覺得那塊講的不明白，我可以持續改進哈。

可以去我的主頁看更多的博客。

云服務器 GPU云服務器我明白了明白人對這些不太明白 python誰講的好

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/37609.html

JavaScript書籍測評

摘要：前言今天和大家一起聊聊的推薦書籍，每一本都是精選，做前端開發的朋友們如果沒讀過，可以嘗試一下。如果怕麻煩，也可以關注曉舟報告，發送獲取書籍，四個字，就可以得到電子書的提取碼。前言今天和大家一起聊聊JavaScript的推薦書籍，每一本都是精選，做前端開發的朋友們如果沒讀過，可以嘗試一下。下面給大家簡單介紹了書的內容，還有讀書的方法，希望可以幫大家提升讀書效率。一、《JavaScr...

X1nFLY 2019-08-21 17:44 評論0 收藏0
輕量級桌面應用開發的捷徑——nw.js

摘要：下面這張解決了怎么用完成任務的問題，最后，開發者怕你懷疑的強大，又提供了幾個和許多成功的案例來打消我們的顧慮。拿下助攻決定用之后，就開始補充相應的知識啦。來欣賞一下一些應用的截圖吧，不得不說開發出的應用一點不比原生的丑陋啊。博客地址每個程序員都希望用自己喜歡的語言，自己喜歡的平臺、工具，寫自己喜歡的程序。于是我們會看到有人在Win下用Visual Studio愉快地coding，也...

pumpkin9 2019-08-21 10:43 評論0 收藏0
Python爬蟲之Scrapy學習（基礎篇）

摘要：下載器下載器負責獲取頁面數據并提供給引擎，而后提供給。下載器中間件下載器中間件是在引擎及下載器之間的特定鉤子，處理傳遞給引擎的。一旦頁面下載完畢，下載器生成一個該頁面的，并將其通過下載中間件返回方向發送給引擎。作者：xiaoyu微信公眾號：Python數據科學知乎：Python數據分析師在爬蟲的路上，學習scrapy是一個必不可少的環節。也許有好多朋友此時此刻也正在接觸并學習sc...

pkhope 2019-07-31 11:05 評論0 收藏0
我的 2017 —— 一個 PHPer 的自白

摘要：大會年，我去了。小會值得一提的是，今年月份，我參加了一個的分享會。出游沙巴這是部門組織的出游，獲得了最佳團隊，拿到了一筆經費，于是有了這次出游。于是，我的下個目的地是西藏。轉眼間 2017 年過去了。我已經不能說自己是去年的畢業生了，時光匆匆，感覺自己越來越老了。這一年，我所經歷的，讓我收獲很多，讓我懂得很多，讓我明白了很多。也許是明確了某一個目標，也許是其它的什么，我覺得，201...

BenCHou 2019-06-28 14:36 評論0 收藏0
(原創)vue 學習筆記

摘要：菜鳥教程這是一個屬性其值是字符串菜鳥教程同上這是一個屬性其值是字符串用于定義的函數，可以通過來返回函數值。它們都有前綴，以便與用戶定義的屬性區分開來。開篇語我最近學習了js,取得進步,現在學習vue.js.建議新手學習,請不要用npm的方式(vue-cli,vue腳手架),太復雜了. 請直接下載vue.js文件本地引入,就上手學習吧參照菜鳥教程網站的vue.js教程http://...

layman 2019-08-22 18:09 評論0 收藏0